# On Eternal Domination of GeneralizedJs,m

Authors: Ramy Shaheen; Mohammad Assaad; Ali Kassem
Journal: Journal of Applied Mathematics
 (2021)

---

## Abstract

An eternal dominating set of a graphG is a set of guards distributed on the vertices of a dominating set so that each vertex can be occupied by one guard only. These guards can defend any infinite series of attacks, an attack is defended by moving one guard along an edge from its position to the attacked vertex. We consider the “all guards move” of the eternal dominating set problem, in which one guard has to move to the attacked vertex, and all the remaining guards are allowed to move to an adjacent vertex or stay in their current positions after each attack in order to form a dominating set on the graph and at each step can be moved after each attack. The “all guards move model” is called the m-eternal domination model. The size of the smallest m-eternal dominating set is called the m-eternal domination number and is denoted by γm∞G. In this paper, we find the domination number of Jahangir graph Js,m for s≡1,2mod3, and the m-eternal domination numbers of Js,m for s,m are arbitraries.


---

## Body

## 1. Introduction

The term graph protection refers to the process of placing guards or mobile agents in order to defend against a sequence of attacks on a network. Go to [1–5] for more background of the graph protection problem. In 2004, Burger et al. [2] introduced the concept of eternal domination. Goddard et al. [3] introduced the “all guards move model” and determined general bounds of γG≤γm∞G≤αG, where αG denotes the independence number of G and γG denotes the domination number of G. The m-eternal domination numbers for cycles Cn and paths Pnwere found by Goddard et al. [3] as follows: γm∞Cn=n/3 and γm∞Pn=n/2. For further information on eternal domination, see survey [1]. The k-dominating graph HG,k was defined by Goldwasser, Klostermeyer, and Mynhardt in [6] as follows: let G be a graph with a dominating set of cardinality k. The vertex set of the k-dominating graph HG,k, denoted VH, is the set of all subsets of VG of the size k which are dominating sets, and two vertices of H are adjacent if and only if the kguards occupying the vertices of G of one can move (at most distance one each) to the vertices of the other, γm∞G≤k if and only if HG,k has an induced subgraph SG,k such that for each vertex x of SG,k, the union of the vertices in the closed neighborhood of x in SG,k is equal to VG.A generalized Jahangir graphJs,mform≥2is a graph on sm+1vertices, i.e., a graph consisting of a cycle Csm with one additional vertex which is adjacent to m vertices of Csm at the distance s from each other on Csm, see [7] for more information on the Jahangir graph. Let vsm+1 be the label of the central vertex and v1,v2,⋯,vsm be the labels of the vertices that incident clockwise on cycle Csm so that degv1=3. We will use this labeling for the rest of the paper. The vertices that are adjacent to vsm+1 have the labels v1,v1+s,v1+2s,..v1+m−1s. We denote the set v1,v1+s,..v1+m−1s by R. So, R=v1+is:i=0,1,..,m−1.Mtarneh, Hasni, Akhbari, and Movahedi claim to have found the domination number ofJs,m in [8] as follows:Theorem 1 [8].
Fors,m≥2,γJs,m=sm/3.However, in this paper, we will prove that this theorem does not hold whens≡1,2mod3.Theorem 2 [3].
(1)γm∞Cn=n3.In a previous paper, we found thatTheorem 3 [9].
(2)γm∞J2,m=3::m=3,γJ2,m:m∈2,4,5,6,7,9,m2+2form≥8andm≠9.Theorem 4 [9].
Form≥2,γm∞J3,m=m+1.


## 2. Main Results

In this section, we prove that Theorem1 does not hold if s≡1,2mod3, and we find γJs,m in these cases; then, we find γm∞Js,m for s≡0,1mod3 and arbitrary m. We also give an upper and a lower bound for the m-eternal domination number of Js,m for s≡2mod3 and arbitrary m.Proposition 5.
Thesm/3−dominatingsetofJs,misuniquefors≡0mod3.Proof.
LetD0 be a dominating set of Js,m with cardinality sm/3. Since s≡0mod3, then sm≡0mod3; therefore, sm/3=sm/3. We imply that the vertices of R that are dominated by vsm+1 separate the cycle Csm into m paths each of which has s−1 vertices and needs s−1/3 vertices to dominate its vertices. If vsm+1∈D0, then we will need at least ms−1/3=sm/3 vertices to dominate the m non-dominated paths of Csm which means we will be needing sm/3+1 vertices, and that is a contradiction. This means D0⊂VCsm. We have three sets of cardinality sm/3 that can dominate the cycle Csm when sm≡0mod3. They are
(3)S1=v1,v4,⋯,vsm−2=v1+3ifori=0,1,⋯,sm3−1,S2=v2,v5,⋯,vsm−1=v2+3ifori=0,1,⋯,sm3−1,S3=v3,v6,⋯,vsm=v3+3ifori=0,1,⋯,sm3−1.
However,D0 must contain at least one vertex adjacent to vertex vsm+1 to dominate it. Since s≡0mod3, then s=3k:k=1,2,⋯,s/3. Since s=3k, then we can obviously see that R=v1+3ik:i=0,1,⋯,m−1andk=1,2,⋯,m−1. However, considering ik>i for k>1, then it is obvious that the set R⊂S1,thereforeS1∩R=R,S2∩R=∅, and S3∩R=∅.Which means only S1 dominates both the cycle Csm and the vertex vsm+1 at the same time. Therefore, D0=S1, and this set is unique.Theorem 6.
γJs,m=ms/3+1ifs≡1mod3.Proof.
LetSbe a set of cardinality ms−1/3+1. Let vsm+1∈S. We imply that the vertices of R that are dominated by vsm+1 separate the cycle Csm into m paths each of which has s−1 vertices and needs s−1/3 vertices to dominate its vertices. We denote these paths by Ti:i=1,..,m. Since s≡1mod3, then s−1≡0mod3; therefore, ms−1/3=ms−1/3 and Ti≡0mod3. Let Si:i=1,..,m be the family of dominating sets of paths Ti:i=1,..,m, respectively. We know that for an arbitrary path Tk, the dominating set is defined as Sk=vsk−1+3,vsk−1+6,..,vks−1, which means S=⋃i=1mSi∪vsm+1 is a dominating set of Js,m with cardinality ms−1/3+1. It is known that the k/3−dominating set of a path Pk:k≡0mod3 is unique; therefore, S is unique because each of Si:i=1,..,m is unique. Let us prove that whatever set Bwhich with cardinality ms−1/3 is not enough to dominate Js,m. We consider the following cases, as illustrated in Figure 1 for J7,4.Case 1.
vsm+1∈B.Figure 1
γJ7,4=ms/3+1=9.In this case, we only havems−1/3−1 vertices to dominate Ti:i=1,..,m which is impossible because it leaves one path Tk with s−1/3−1 dominating vertices, which means three vertices of Tk will not be dominated, and that is a contradiction.Case 2.
vsm+1∉B.In this case,⊂VCsm. We know that γCsm=sm/3. However, sm/3 is one of the following:
(4)sm3=sm3;sm≡0mod3,sm+23;sm≡1mod3sm+13;sm≡2mod3.,It is obvious thatsm/3>ms−1/3forallcasesofsm, which means B cannot dominate all the vertices of Csm. Therefore, B cannot dominate Js,m entirely. From Case 1 and Case 2, we imply that γJs,m>ms−1/3fors≡1mod3. Hence, ms−1/3<γJs,m≤ms−1/3+1 which means γJs,m=ms−1/3+1. However, s−1/3=s/3fors≡1mod3; therefore, γJs,m=ms/3+1fors≡1mod3.Theorem 7.
γJs,m=sm−m/2/3+1ifs≡2mod3.Proof.
We know that a setD0 of sm/3 vertices can dominate Csm. Let us identify D0 as D0=A∪vsm=v3k:1≤k≤sm−2/3∪vsm. Since v1+s=v1+3l+2=v31+l∈D0, therefore D0 dominates vsm+1 which means it dominates Js,m entirely. However, let us consider another dominating set D1 of cardinality sm/3+1, where D1=D0∪vsm+1. We consider the two following cases:Case 1.
m is even.Let us prove that we can derive a dominating setD2 of cardinality sm−m/2/3+1 from D1. Since vsm+1∈D1, it is obvious that vsm+1 dominates all the vertices of R; therefore, vsm+1 dominates v1,v1+s,v1+2s. Let us consider the first two paths T1,T2 identified in Theorem 6. We notice that D1∩VT1=v3,v6,..,vs−2, while D1∩VT2=vs+4,vs+7,..,v2s−1 and v1+s∈D1. We need v1+s to dominate vs and v2+s so we include it in our new set D2. However, since v2s,v1+2s are dominated by v2s−1,vsm+1, respectively, then we do not need to add v2+2s to D2; therefore, we can start D2∩VT3 with v3+2s and recreate the same distribution of dominating sets we used on the unit {T1,v1+s,T2}. This distribution spares one vertex (v1+2s) from the need of being protected by a dominating vertex from Csm. Without loss of generality, we can use this distribution for every two consecutive paths of Csm, since we have m paths, and m is even, and this distribution spares m/2 vertices from the need of being dominated by a dominating vertex from Csm; therefore, D2=sm−m/2/3+1.Case 2.
m is odd.We use the same discussion in Case1 on paths (T1,..,Tm−1), but since we have one additional path (Tm), we will have one less vertex to spare from the need of being dominated by a dominating vertex from Csm; therefore, D2=sm−m−1/2/3+1 in this case.From Cases1 and 2, we imply that sm−m/2/3+1 vertex can dominate Js,mifs≡2mod3; therefore,
(5)γJs,m≤sm−m/23+1ifs≡2mod3.LetX be a set of cardinality sm−m/2/3, and we consider the following cases:Case 1.
vsm+1∈X.In this case, there will be at least two nondominated vertices ofCsm even after applying the strategy we showed earlier.Case 2.
vsm+1∉X.In this case,X∩Csm=X, and since X=sm−m/2/3 and γCsm=sm/3, we have a contradiction.We conclude from both Case1 and Case 2 that
(6)γJs,m≥sm−m/23+1ifs≡2mod3.From (5) and (6), we conclude that γJs,m=sm−m/2/3+1ifs≡2mod3.Theorem 8.
γm∞Js,m≤sm/3+1fo(7)rs≥3,m≥2.Proof.
From Theorem2, we have γm∞Csm=sm/3. With the right distribution of the required sm/3 guards on the vertices of the outer cycleCsm and placing one additional guard on the central vertex vsm+1, this additional guard would not have to move to defend any attack on the vertices of Csm since sm/3 guards are enough to eternally dominate the vertices of Csm. The vertexvsm+1 cannot be attacked because it is occupied which means γm∞Js,m≤sm/3+1.Theorem 9.
γm∞Js,m=sm/3+1ifs≡0mod3.Proof.
From Theorem1, we know that γJs,m=sm/3fors≡0mod3. We imply that Theorem 7 that S0=v1,v4,⋯,vsm−2 is the unique sm/3−dominating set of Js,m. We consider an attack on an arbitrary vertex v2∈VCsm−S0. The only guard that can move to v2 to defend the attack is the guard located on v1. We can only consider the two following strategies:
Strategy 1: we move the guard fromv1 to v2 without moving any other guard and that would leave vsm unprotected.
Strategy 2: we make a full rotation (clockwise) from the vertices of setS0 to the vertices of the only set that contains v2 and can dominate Csm as well. This required set is the set S2=v2,v5,⋯,vsm−1=v2+3i:i=0,1⋯,sm/3−1. But from Theorem 7, we imply that S2∩R=∅; therefore, the central vertex vsm+1 will not be protected anymore. Without loss of generality, both strategies fail for any vertex vi∈VCsm−S0, and we conclude that γm∞Js,m>sm/3fors≡0mod3. From Theorem 8, we know the result that γm∞Js,m≤sm/3+1fors≡0mod3. Then, γm∞Js,m=sm/3+1fors≡0mod3, see Figures 2 and 3.Lemma 10.
For any path,Pk:k≡0mod3 with the k/3−dominating set S=v2,v5,⋯,vk−1 and for any vertex vi∈S, if vi−1,vi+1 is attacked, then there is a way to move the guards to keep all vertices of Pk protected with the exception of vk,v1, respectively.Proof.
It is obvious that any pathPk:k≡0mod3 can be divided into k/3 subsets each of which contains three vertices. To dominate each subset, we need only one guard located on the middle vertex, so each vertex vi∈S dominates itself, vi−1,vi+1.Figure 2
ForJ6,4;s≡0mod3.Figure 3
ForJ6,4;s≡0mod3.Ifvi−1 is attacked, then the guard on vi moves to vi−1 which would leave vi+1 unprotected. However, the guard on vi+3 moves to vi+2, and so all the guards need to move one step to the left which means the guard on vk−1 moves to vk−2 leaving vk unprotected.Ifvi+1 is attacked, then the guard on vi moves to vi+1 which would leave vi−1 unprotected. However, the guard on vi−3 moves to vi−2, and so all the guards need to move one step to the right which means the guard on v2 moves to v3 leaving v1 unprotected.Theorem 11.
γm∞Js,m=ms/3+2 for s≡1mod3.Proof.
LetJs,mbe a Jahangir graph with s≡1mod3, and let S be the unique dominating set of cardinality ms/3+1 for Js,mthat was identified in Theorem 9. We position a guard on each vertex of S. Since S is unique, then it will fail at defending Js,m against the first attack. We study a series of arbitrary attacks on Js,m denoted by (A1,A2,⋯,Ai,⋯), and we assume that A1 occurs on vl∈R; then, the only guard capable of defending the attack is located on vsm+1 but moving this guard to vl would leave the remaining vertices of R unprotected. And since we cannot bring any other guard to vsm+1 to protect them which means γm∞Js,m≠ms/3+1, but from the definition of Jahangir graph and also from Theorem 8, we can easily find that γm∞Js,m≥ms/3+1 which means
(8)γm∞Js,m>ms3+1.We add a guard on an arbitrary vertexy∈R so the new set of guards consisting of ms/3+2 guards is S∪y. We will denote this distribution of guards by M0.We notice that the vertices ofR partition Js,m are into m subgraph of s+2 vertices so that vsm+1 belongs to every subgraph. We denote these subgraphs by SJi:i=1,..,m. We have
(9)SJ1=v1,⋯,vs+1,vsm+1,SJ2=vs+1,⋯,v2s+1,vsm+1,SJm=vm−1s+1,⋯,vsm,v1,vsm+1.We assumeA1 occurs on a vertex vi∈SJ1, and that y∉SJ1; then, the guard set on SJ1 is v3,v6,⋯,vs−1, and we consider the following cases:Case 1.
vi−1 is occupied.In this case, the only guard capable of moving tovi is located on vi−1 which leaves vi−2 unprotected and in order to protect it, the guard on vi−4 moves to vi−3, as in Lemma 10 which all the guards located on vertices of T1 move one step towards the higher index which leaves the end vertex with the lowest index v2 unprotected, and the guard on vsm+1 is the only one capable of moving directly to v1 to protect v2. This is possible because of v1∈R, and this movement will make R−v1,y unprotected. To avoid that, we move the guard on y to vsm+1 to protect all the vertices of R. So, the new set of guards located on SJ1 is
(10)W1=v1,v4,v7⋯,vs−3,vs,vsm+1.We assume the attacksA2,A3,⋯ occur on SJ1 as well. We notice that the previous distribution W1 with the two following distributions:
(11)W2=v2,v5,v8⋯,vs−2,vs+1,vsm+1,W3=v3,v6,v9⋯,vs−1,vs+1,vsm+1.Form an eternal dominating family on SJ1 for the following reasons:
(i)
Each two sets ofW1,W2,W3 are reachable from each other in one step, see Figure 4(12)VW1∪VW2∪VW3=VSJ1.Figure 4
γm∞J7,4=ms/3+2=10.It is obvious thatW3 is a special case of M0, because y∈v1,vs+1 in W3, while y∈R in M0.After a series of attacks onSJ1, we assume an attack Al occurs on vk∈SJk:k≠1, because each one of W1,W2,W3 contains vsm+1 and a vertex of R (v1orvs+1); then, it is possible to repeat the same previous strategy to defend the attack A1 and apply it to SJk. When trying to defend Al, the guard of R that moves to v1+sk−1 to protect v2+sk−1 is the vertex y∈v1,vs+1 taking into consideration that the distributions W1−y, W2−y can move back to M0 in one step while W3 is already a special case of M0. Without loss of generality, this strategy applies to every subgraph SJk, and any series of attacks taking into consideration that the proof does not change if y∈SJ1 when A1 occurs (in this case, we start at W3 instead of M0).Case 2.
vi+1 is occupied.By following the same process in Case1 with one difference which is moving the guards of T1towards the lower index when defending A1, vs becomes unprotected, as in Case 1, and the guard on vsm+1 moves to vs+1 to protect vs, and y moves to vsm+1 forming W2, in a similar way to Case 1. W1,W2,W3 form an eternal dominating family on SJ1, and the same argument about Al can be followed here.Case 3.
vi∈R.
WhenA1 occurs, we consider the following subcases:
Case 3(a). The current distribution is M0, and then the guard set is S∪y.The guard on vsm+1 moves to vi, the guard on y moves to vsm+1, and the new set of guards is S∪vi; therefore, we remain in M0.
Case 3(b). The current distribution is W1 in the previously attacked subgraph, and let us assume this subgraph is SJ1 while the remaining subgraphs fall under M0; then, the guard on vsm+1moves to vi, the guard on v1 moves to vsm+1 to defend the attack, and the guards W1−y move back toM0 so the new set of guards is S∪vi; therefore, we remain in M0. Without loss of generality, this strategy applies no matter which subgraph was attacked in the previous attack.
Case 3(c). The current distribution is W2 in the previously attacked subgraph, and we use the same argument in Case 3(b).From all the previous cases, we can see thatms/3+2 guards can eternally dominate Js,m. Therefore,
(13)γm∞Js,m≤ms3+2.From (8) and (13), we conclude that γm∞Js,m=ms/3+2 for s≡1mod3. Figure 4 also demonstrates how 10 guards can move directly from any guard distribution of SJ1 to the distribution W1 of SJ4, and this direct transportation can occur from every guard distribution of any subgraph SJk to all other distributions of every subgraph SJk:2≤k≤m.Corollary 12.
(14)γm∞Js,m=sm3+1fors≡0mod3,ms3+2fors≡1mod3,sm−m/23+1≤γm∞Js,m≤sm3+1.Proof.
We conclude 1 by combining Theorems9 and 11.
We know thatγm∞Js,m≥γJs,m; therefore, from Theorems 7 and 8, we conclude 2.



---

*Source: 8882598-2021-03-18.xml*