# The Numerical Invariants concerning the Total Domination for Generalized Petersen Graphs

Authors: Taiyin Zhao; Gohar Ali; Nabila Hameed; Syed Inayat Ali Shah; Yu-Ming Chu
Journal: Journal of Mathematics
 (2020)

---

## Abstract

A subsetS of VG is called a total dominating set of a graph G if every vertex in VG is adjacent to a vertex in S. The total domination number of a graph G denoted by γtG is the minimum cardinality of a total dominating set in G. The maximum order of a partition of VG into total dominating sets of G is called the total domatic number of G and is denoted by dtG. Domination in graphs has applications to several fields. Domination arises in facility location problems, where the number of facilities (e.g., hospitals and fire stations) is fixed, and one attempts to minimize the distance that a person needs to travel to get to the closest facility. In this paper, the numerical invariants concerning the total domination are studied for generalized Petersen graphs.


---

## Body

## 1. Introduction

Graph theory has been used to study various concepts of partition of the vertex set for the graphG [1–3]. The domination (total domination) problem for the graph was studied from 1950s onward, and domination (total domination) in graphs is said to be NP-complete problem [4]. Domination (total domination) sets are of practical interest in several areas of mathematics and other branches of science [5, 6]. In wireless networks, dominating (total dominating) sets are used to find efficient routes within ad hoc mobile networks. In documents’ summarization, domination (total domination) sets are used. Dominating (total dominating) sets are closely related to independent sets. Total dominating set is independent if and only if it is a maximal input set [7].Moreover, in computer science, weighted graphs are widely used in the developments of data mining, software testing, image processing, communication networks, and information security [8–11].In this paper, the numerical invariants concerning the total domination are studied for generalized Petersen graphs [12–16].


## 2. Preliminaries

LetG=V,E be a simple, undirected, and finite graph with the vertex set VG and the edge set EG.The (open) neighborhood of a vertexu∈VG, denoted by Nu, is the set of all vertices adjacent to u, i.e., Nu=v∈VG:uv∈EG. The closed neighborhood of u is defined as Nu=u∪Nu [17–19]. For a set S⊆VG, its open neighborhood is the set NS=∪u∈SNu, and its closed neighborhood is the set NS=NS∪S. A dominating set of a graph G, abbreviated as DS, is a set S of vertices in G such that every vertex in VG\S is adjacent to a vertex in S. The domination number of a graph G, denoted by γG, is the minimum cardinality of a dominating set. A total dominating set of a graph G, abbreviated as TDS, is a set S of vertices in G such that every vertex in VG is adjacent to a vertex in S. If no proper subset of S is a TDS of G, then S is a minimal TDS of G. Every graph without isolated vertices has a TDS. The total domination number of a graph G, denoted by γtG, is the minimum cardinality of a TDS. A TDS of G of minimum cardinality is called a γtG-set.The concept of total domination was introduced by Cockayne et al. [20]. For more information, see [21, 22].LetτG be the total number of γtG-sets. For each vertex v∈VG, we define the total domination value of v, denoted by TDVGv, to be the number of γtG-sets to which v belongs. Evidently, 0≤TDVGv≤τG for any G and any v∈VG.Generalized Petersen graphs are important classes of commonly used interconnection networks and have been intensively studied. The generalized Petersen graphPn,m, n≥3 and 1≤m≤⌊n−1/2⌋, consists of an outer n-cycle u1,u2,…,un, a set of n spokes uivi, 1≤i≤n, and n edges vivi+m, 1≤i≤n, with indices taken as modulo n, see Figure 1. Thus, its vertex set is the union of U=u1,u2,…,un and V=v1,v2,…,vn. We say that the first set consists of u vertices and the second one of v vertices. By a u-path in Pn,m, we mean a path whose vertices consist of just u-vertices. A v-path is defined similarly. The generalized Petersen graph Pn,m is shown in Figure 1.Figure 1
Generalized Petersen graphPn,m.Investigation of the total number of total domatic sets and the total number of total dominating sets of the generalized Petersen graph is the sole aim and interest of writing this paper. Cao et al. in [23] studied the total domination number of generalized Petersen graphs and obtained the exact value of γtPn,2. For k≥2, they proved(1)γtPn,2=2k,forn=3k,2k+2,forn=3k+1,2k+2,forn=3k+2.In this paper, we determine the exact values forγtPn,m when n≡0mod3 and m≠0mod3 and when m=4,5,and7. We also investigate total number of total dominating sets for these cases.


## 3. Main Results

The following result provides a trivial lower bound on the total domination number of a graph in terms of the maximum degree of the graph.Theorem 1.
(see [24]). If G is a graph with no isolated vertex and maximum degree ΔG, then(2)γtG≥VGΔG.Theorem 2.
LetPn,m be a generalized Petersen graph with n=3k≥6, k≥2. If m≠0mod3, then(3)γtPn,m=2n3=2k.Proof.
Letn=3k≥6. According to Theorem 1, we get(4)γtPn,m≥VP3k,m3=6k3=2k.
Thus, to prove the equality, we just need to find a total dominating set of cardinality2k. Let us consider a set(5)S=u3j+1,v3j+1:j=0,1,…,k−1.
The vertexu3j+1, j=0,1,…,k−1, dominates vertices v3j+1, u3j, and u3j+2, and the vertex v3j+1, j=0,1,…,k−1, dominates vertices u3j+1, v3j+1+m, and v3j+1−m with indices taken as modulo n. It is easy to see that, as m≠0mod3, all vertices in P3k,m are dominated. Thus, S is a total dominating set, and S=2k. This concludes the proof.
Now, we proceed form=4.Theorem 3.
LetPn,4 be a generalized Petersen graph; then,(6)γtPn,4=2k,forn=3k,k≥2,2k+4,forn=3k+1,k≥7,2k+4,forn=3k+2,k≥7.Proof.
Let us consider three cases:Case 1: whenn=3k, k≥2, the result follows from Theorem 2.Case 2: whenn=3k+1, k≥7, without loss of generality, consider a set S0=u3j+1,v3j+1:j=0,1,…,k. The vertex u3j+1, j=0,1,…,q, dominates vertices v3j+1, u3j, and u3j+2, and the vertex v3j+1, j=0,1,…,q, dominates vertices u3j+1, v3j+4, and v3j−3 with indices taken as modulo n. Thus, the vertices from this set S0 dominate all but two vertices in G. The two vertices which are not dominated are v2 and vn−1. To totally dominate v2 and vn−1, we add their neighbors u2 and un−2 to S0 because these two vertices are already adjacent vertices in S0. This means that the set S=S0∪u2,un−2 totally dominates all vertices in G. Thus, γtP3k+1,4≤S=2k+4.For necessity, we need to prove the reverse inequality, i.e.,γtP3k+1,4≥2k+4. The proof will be by mathematical induction. For n=22, the result is obvious.Since the result is true for allPn,4 of the number of vertices less than n when m≡0mod3, for n≡1mod3, let D be any total dominating set of Pn,4. Then, D=D1∪u2∪un−2∪un∪vn, where D1 is the total dominating set of Pn,4 if only n≡0mod3, and we get D1≥⌈2n−2/3⌉=2k. Thus, we proved our required assertion.Case 3: whenn=3k+2, k≥4, without loss of generality, consider a set S0=u3j+1,v3j+1:j=0,1,…,k. The vertex u3j+1, j=0,1,…,q, dominates vertices v3j+1, u3j, and u3j+2, and the vertex v3j+1, j=0,1,…,q, dominates vertices u3j+1, v3j+4, and v3j−3 with indices taken as modulo n. Thus, the vertices from this set S0 dominate all but two vertices in G. The two vertices which are not dominated are v2 and vn−2. To totally dominate v2 and vn−2, we add these two vertices to S0 because these two vertices are adjacent. This means that the set S=S0∪v2,vn−2 totally dominates all vertices in G. Thus, γtP3k+2,4≤S=2k+4.
For necessity, we need to prove the reverse inequality, i.e.,γtP3k+2,4≥2k+4. The proof will be by mathematical induction.
Assume the result is true for allPn,4 of the number of vertices less than n. For n≡2mod3, let D be any total dominating set of Pn,4. Then, D=D1∪u2∪un−2∪un−1∪vn−1, where D1 is the total dominating set of Pn,4 if only n≡0mod3, and then D1≥⌈2n−2/3⌉=2k, i.e., D≥2k+4.Theorem 4.
LetPn,m be a generalized Petersen graph. Then, dtPn,m=3 if n≡0 (mod 3) and m≠3q.Proof.
LetP1,P2,P3 be the total domatic partitions since no vertex of any partition is contiguous to any other partitions and all the three domatic partitions totally dominate GPn,m. Also, we know that TDVui=TDVvi=1. We proved in Theorem 6 in the following that τPn,m=3 if only n≡0 (mod 3). It is observed that there is no recurrence in the total number of total dominating sets. Hence, we can write dtPn,m=τPn,m=3 if only n≡0 (mod 3).
Henning and Yeo [24] proved the following.Theorem 5.
(see [24]). For any connected graph G,(7)∑v∈VGTDVGv=τG⋅γtG.Theorem 6.
Letn≠10 and m≥4 be positive integers. If m≠0mod3, then(8)τPn,m=3,forn≡0mod3,n,forn≡0mod3,where for m=5, n must be odd.Proof.
Letm≥4 be a positive integer, m≠0mod3.Case 1: whenn=3k, k≥2, then γtPn,m=2k, and a γtPn,m-set Γ comprises kP2’s, and Γ is fixed by the choice of the first P2. There is exactly one γtPn,m-set comprising vertices u1 and v1. Thus, TDVu1=TDVv1=1. Similarly, TDVu2=TDVv2=1,…,TDVun=TDVvn=1. Using Theorem 5, we get(9)∑i=12n1=2k⋅τPn,m,2n⋅1=2k⋅τPn,m.Hence,τPn,m=3 in this case.Case 2: whenn=3k+1 or n=3k+2, then a γtPn,m-set Γ is composed of in exactly one of the following ways:(1)
Γ comprises kP2’s and one P4(2)
Γ comprises k−1P2’s and two P3’s(3)
Γ comprises k−1P2’s and one P4(4)
Γ comprises k−1P2’s and two P4’s(5)
Γ comprises k+1P2’s
Now, we discuss these subcases.(i)
Subcase 1: whenΓ≡kP2∪P4, note that Γ is fixed by the choice of single P4. Selecting P4 is the same as selecting its initial vertex in the counterclockwise order; thus, τPn,m=n.(ii)
Subcase 2: whenΓ≡k−1P2∪2P3, the set Γ is fixed by the choice of two P3’s, and there are n options for choosing the first two P3’s; thus, τPn,m=n.(iii)
Subcase 3: whenΓ≡k+1P2∪P4, there is only one chance for choosing single P4 and k+1 chances for choosing P2. Each vertex has equal number of chances. Each vertex is equally repeated in the total number of total dominating sets three times; thus, the total number of total dominating sets will be n.(iv)
Subcase 4: whenΓ≡k−1P2∪2P4, then Γ is fixed by the choice of double P4. Each vertex is repeated three times in the total number of dominating sets, and for each vertex, there are equal number of chances for total domination; hence, each TDS will be repeated n times.(v)
Subcase 5: whenΓ≡k+1P2, there are exactly two vertices in each P2. Each vertex of P2 dominates three vertices including the vertex itself because this is a 3-regular graph. Thus, there are n number of choices for the total number of dominating sets; thus, in all cases, τPn,m=n.Corollary 1.
LetPn,5 be a generalized Petersen graph; then,(10)γtPn,5=4k+4,forn=6k+1,k≥2,4k+4,forn=6k+5,k≥1.Proof.
The proof is similar to the proof of Theorem3.Corollary 2.
LetPn,7 be a generalized Petersen graph; then,(11)γtPn,7=2k+6,forn=3k+1,k≥5,2k+6,forn=3k+2,k≥5.Proof.
The proof is similar to the proof of Theorem3.


## 4. Total Domatic Number of a Graph

The total domatic number of a graphG is denoted by dtG and is defined as dtG=s, where VG=∪i=1sDi and Di′s are the total dominating sets and are the maximum disjoint partition of the vertex set of the graph.Proposition 1.
For any simple graphG with minimum degree δG, the total domatic number dtG≤δG.In the following result, our proof is simple from the proof of [25].Theorem 7.
(see [25]). For a graph G of order n and minimum degree δG, the lower bound for the total domatic number dtG≥⌊n/n−δG+1⌋, where n−δG+1=dtG.Proof.
LetD be the total dominating set of the graph G and Gc be the complement of G. If δG is the minimum degree of G, then n−δG−1 is the maximum degree of Gc, and due to this, any vertex x of the graph G is adjacent to at most n−δG−1 vertices of D in Gc. If the vertex x∈D, then a vertex z of the graph exists which is not adjacent to x in Gc but xz∈EG; this confirms that D≥n−δG+1, and hence, dtG≥⌊n/n−δG+1⌋.Corollary 3.
ForG=Pn,m generalized Petersen graph of order 2n and δG=3, we have 1≤dtG≤3.


## 5. Open Problems

We conclude the paper with the following open problems for further investigation.Open Problem 1.
CharacterizeγtPn,m for all feasible values of n and m.Open Problem 2.
CharacterizeTDVu for each u∈VPn,m.


### 5.1. Discussion

In this paper, the generalized Petersen graphPm,n is investigated for the total domination number γt, total number of dominating sets τ, and total domatic number dtPn,m. Here, we found the total dominating number for some restricted values of m∈ℤ+. For detailed applications of our results, refer [26–28].


## 5.1. Discussion

In this paper, the generalized Petersen graphPm,n is investigated for the total domination number γt, total number of dominating sets τ, and total domatic number dtPn,m. Here, we found the total dominating number for some restricted values of m∈ℤ+. For detailed applications of our results, refer [26–28].



---

*Source: 5473675-2020-10-24.xml*