# Eternal Domination of Generalized Petersen Graph

Authors: Ramy Shaheen; 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 γm∞Pn,1 and γm∞Pn,3 for n≡0mod4. We also find upper bounds for γm∞Pn,2 and γm∞Pn,3 when n is arbitrary.


---

## 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. Burger et al. introduced the concept of eternal domination in 2004 [2]. Goddard et al. introduced the “all guards move model” in [3]. General bounds of γG≤γm∞G≤αG were determined in [3], 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 Pn were 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]. A generalized Petersen graph Pn,k is a graph with vertex set V∪U=v1,v2,⋯,vn∪u1,u2,⋯,un and edge set E=∪vivi+1,viu1,uiui+k with vn+1=v1, un+1=u1, and 1≤i≤n and 1≤k≤n/2; see [6] for more information on generalized Petersen graph. The k-dominating graph HG,k was defined by Goldwasser et al. in [7] 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 size k which are dominating sets and two vertices of H are adjacent if and only if the k guards 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 subgraphSG,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 graph Js,m for m≥2 is a graph on sm+1 vertices, i.e., a graph consisting of a cycle Csm with one additional vertex which is adjacent to m vertices of Csm at distance s from each other on Csm; see [8] for more information on the Jahangir graph. In [9], we found γm∞Js,m for s≡2,3. In [10], we found γm∞Js,m for s,m are arbitraries.Proposition 1 [11].
Forn≥3, we have γPn,1=n/2forn≡0,1,3mod4,n/2+1forn≡2mod4.Proposition 2 [11].
Forn≥5, we have γPn,2=3n/5.Proposition 3 [11].
Forn≥7, we have γPn,3=n/2+1forn≡2mod4,n/2forn≡0,1mod4orn=11,n/2+1forn≡3mod4,n≠11.Proposition 4 [12].
Forn≥5, we have αPn,2=4n/5.Proposition 5 [12].
Forn≥7, we have αPn,3=nifniseven,n−2ifnisodd.Proposition 6 [3].
For any graphG:γG≤γm∞G≤αG.


## 2. Main Results

### 2.1. Eternal Domination Number ofPn,1

In this section, we find them-eternal domination number of Pn,1 for n is arbitrary.Theorem 1.
γm∞Pn,1=n/2forn≡0,1,3mod4,n/2+1forn≡2mod4.Proof.
We consider all four cases ofn.Case 1 (n≡0mod4).
Letn=4l:l∈N. As it was found in [11] that γPn,1=n/2 for this specific case and the γ-dominating set S is the union of two sets A and B which are A=v4i+1;0≤i≤l−1, B=u4i+3;0≤i≤l−1.We form thek-dominating graph HG,k where G=Pn,1, k=n/2, and with sets
(1)D1=A1∪B1=v4i+1;0≤i≤l−1∪u4i+3;0≤i≤l−1,D2=A2∪B2=v4i+2;0≤i≤l−1∪u4i+4;0≤i≤l−1,D3=A3∪B3=v4i+3;0≤i≤l−1∪u4i+1;0≤i≤l−1,D4=A4∪B4=v4i+4;0≤i≤l−1∪u4i+2;0≤i≤l−1.Each of these setsD1,D2,D3,D4 has a cardinality of n/2 and they are adjacent in HPn,1,n/2 for the following reasons.D1⟶D2, D2⟶D3, D3⟶D4, D4⟶D1 by rotating the guards one step clockwise.D2⟶D1, D3⟶D2, D4⟶D3, D1⟶D4 by rotating the guards one step counterclockwise.D1⟶D3, D3⟶D1, D2⟶D4, D4⟶D2 by reflection which means moving the guards one step to occupy the corresponding unoccupied vertex on the other cycle.Therefore,D1,D2,D3,D4 are adjacent in SPn,1,n/2 (the induced subgraph of HPn,1,n/2) on D1,D2,D3,D4 and D1∪D2∪D3∪D4=VPn,1; therefore, we conclude that γm∞Pn,1≤n/2forn≡0mod4 but γm∞Pn,1≥γPn,1 from the definition of eternal domination; therefore, γm∞Pn,1=γPn,1=n/2 for n≡0mod4; see Figure 1.Case 2 (n≡1mod4).
Letn=4l+1:l∈N. It was found in [11] that γPn,1=n/2 for this case and it was found that the γ-dominating set S is S=A∪B∪x:x∈vn,un.Figure 1
γm∞P12,1=γP12,1=6.We form thek-dominating graph HPn,1,n/2 with the following sets of cardinalityn/2:
(2)D1=v4i+1;0≤i≤l−1∪u4i+3;0≤i≤l−1∪vn,D2=v4i+2;0≤i≤l−1∪u4i+4;0≤i≤l−1∪un,D3=v4i+3;0≤i≤l−1∪u4i+1;0≤i≤l−1∪un,D4=v4i+4;0≤i≤l−1∪u4i+2;0≤i≤l−1∪vn.It is easy to notice thatD1,D2,D3,D4 are all adjacent in HPn,1,n/2 and the union D1∪D2∪D3∪D4=VPn,1; therefore, γm∞Pn,1≤n/2 for n≡1mod4 but we have γm∞Pn,1≥γPn,1 from the definition of eternal domination; therefore, γm∞Pn,1=γPn,1=n/2 for n≡1mod4; see Figure 2.Case 3 (n≡2mod4).
Letn=4l+2:l∈N. As it was found in [11], γPn,1=n/2+1 for this specific case and the γ-dominating set S is S=A∪B∪x,y:x,y∈vn−1,vn,un−1,un.Figure 2
γm∞P13,1=γP13,1=7.We form thek-dominating graph HPn,1,n/2+1 with the following sets of the cardinality n/2+1:
(3)D1=v4i+1;0≤i≤l−1∪u4i+3;0≤i≤l−1∪vn−1,un,D2=v4i+2;0≤i≤l−1∪u4i+4;0≤i≤l−1∪vn,un,D3=v4i+3;0≤i≤l−1∪u4i+1;0≤i≤l−1∪vn−1,un−1,D4=v4i+4;0≤i≤l−1∪u4i+2;0≤i≤l−1∪vn,un−1.It is easy to notice thatD1,D2,D3,D4 are all adjacent in HPn,1,n/2+1 and the union of sets D1∪D2∪D3∪D4=VPn,1; therefore, γm∞Pn,1≤n/2+1 for n≡1mod4, γm∞Pn,1≥γPn,1; therefore, γm∞Pn,1=γPn,1=n/2+1; see Figure 3.Case 4 (n≡3mod4).
Letn=4l+3:l∈N. Ebrahimi et al. found in [11] that γPn,1=n/2 for this case and the γ-dominating set S is S=A∪B∪x,y:x,y∈vn−2,vn−1,vn,un−2,un−1,un.Figure 3
γm∞P14,1=γP14,1=8.We form thek-dominating graph HPn,1,n/2 with the following sets of cardinality n/2:
(4)D1=v4i+1;0≤i≤l−1∪u4i+3;0≤i≤l−1∪vn−2,un,D2=v4i+2;0≤i≤l−1∪u4i+4;0≤i≤l−1∪vn−1,un,D3=v4i+3;0≤i≤l−1∪u4i+1;0≤i≤l−1∪un−2,vn,D4=v4i+4;0≤i≤l−1∪u4i+2;0≤i≤l−1∪vn−1,vn.It is easy to notice thatD1,D2,D3,D4 are all adjacent in HPn,1,n/2 and the union D1∪D2∪D3∪D4=VPn,1; therefore, γm∞Pn,1≤n/2 for n≡3mod4 but γm∞Pn,1≥γPn,1; therefore, γm∞Pn,1=γPn,1=n/2 for n≡3mod4; see Figure 4. From Cases 1–4, we conclude that γm∞Pn,1=γPn,1 for n≥3.Figure 4
γm∞P15,1=γP15,1=8.


### 2.2. Eternal Domination Number ofPn,2

In this section, we give an upper bound for the eternal domination number of generalized Petersen graphPn,2.Lemma 1.
If we dividePn,2 into n/5 blocks where each block consists of 10 vertices (5 vertices from the outer cycle and their 5 adjacent vertices from the inner cycle), then 4 guards are enough to eternally dominate each block.Proof.
We denote these blocks byBj:1≤j≤n/5; we also denote the subblock that remains in case n≢0mod5 by SB keeping in mind that SB consists of 2, 4, 6, and 8 vertices when we have n≡1,2,3,4mod5, respectively. It was found in [11] that three vertices are enough to dominate each block Bj if the dominating vertices were distributed as shown in Figure 5.Figure 5
DominatingBj with 3 vertices.To prove that four guards can eternally protect any blockBj it is enough to find a set of configurations for the guards so that these configurations cover all the vertices of Bj (every vertex of Bj belongs to at least one configuration) and every two configurations are reachable from each other in one step; we notice that the configurations presented in Figure 6 can achieve that; therefore, according to the definition of the k-dominating graph, we conclude that γm∞Bj≤4.Theorem 2.
Forn≥5,
(5)γm∞Pn,2=4;nϵ5,6,γm∞P7,2=5,γm∞P8,2∈5,6,γm∞Pn,2≤3n5+n10;n≥9andn≡0mod10,γm∞Pn,2≤3n5+n10;n≥9andn≡0mod5andn≢0mod10,γm∞Pn,2≤3n5+n10+l;n≡lmod10andl=1,2,3,γm∞Pn,2≤3n5+n10+l;n≡lmod5andn≢lmod10andl=1,2,3,γm∞Pn,2≤3n5+n10+2;n≡4mod10,γm∞Pn,2≤3n5+n10+3;n≡4mod5andn≢4mod10.Proof.
We discuss all the cases as follows.
Case i.1 (n=5).
From Propositions2, 4, and 6, we conclude that
(6)3≤γm∞P5,2≤4.
By formingHPn,2,3 (the 3-dominating graph for Pn,2), we notice that VHPn,2,3 consists of the following sets:
(7)D1=v1,u3,u4,D2=v2,u4,u5,D3=v3,u1,u5,D4=v4,u1,u2,D5=v5,u2,u3,D6=v1,v3,u2,D7=v2,v4,u3,D8=v3,v5,u4,D9=v1,v4,u5,D10=v2,v5,u1.
Figure7 illustrates HPn,2,3.
We denote the closed neighborhood of vertexDi in HPn,2,3 by Xi, and we notice the following:
(8)u1∉X1,u2∉X2,u3∉X3,u4∉X4,u5∉X5,v2∉X6,v3∉X7,v4∉X8,v5∉X9,v1∉X10.
Therefore, by the definition ofk-dominating graph, we conclude that γm∞P5,2≠3 which means γm∞P5,2=4 from (6).
We can easily prove that the following family is a 4-vertex eternal dominating family ofP5,2:(9)D1=v1,v2,u4,u5,D2=v4,v5,u1,u2,D3=v1,v3,u3,u4.
Case i.2 (n=6).
From Propositions2, 4, and 6, we conclude that 4≤γm∞P6,2≤4 which means γm∞P6,2=4 and the following family is a 4-vertex eternal dominating family of P6,2:(10)D1=v1,v4,u3,u6,D2=v2,v5,u1,u4,D3=v3,v6,u2,u5.
Case ii (n=7).
From Propositions2, 4, and 6, we conclude that γm∞P7,2=5. The following family is a 5-vertex eternal dominating family of P7,2:
(11)D1=v1,v4,v6,u3,u7,D2=v2,v5,v7,u1,u2,D3=v3,v7,u4,u5,u6.
Case iii (n=8).
From Propositions2, 4, and 6, it can be implied that
(12)5≤γm∞P8,2≤6.
Case iv (n≡0mod10).
In this case, we have an even number of blocks that were defined in Lemma1. For every pair of adjacent blocks, let us assign 3 guards to one of them and 4 guards to the other; we start by studying the first two blocks B1,B2; to prove that the 7 guards assigned to these two blocks are enough to eternally protect them, it is enough to find a set of guard configurations for which every vertex of VB1∪VB2 belongs to at least one of the configurations and every two configurations are reachable from one another in one step. We imply that the configurations shown in Figure 8 satisfy this purpose.
Therefore, the number of guards we assigned toB1,B2 is enough to eternally protect these two blocks. Let us now consider the next attack to occur on a vertex that does not belong to any of these two blocks; for example, the vertex denoted by v18 which is the middle “outer” vertex of B4 and then the guards of B1,B2 return to configuration 1 of Figure 7 and at the same time the guards of B3,B4,B5,B6 move to configuration 3 of Figure 7. It is obvious that these configurations can be applied to all sets of blocks in Pn,2 which means without loss of generality the theory holds and we conclude that γm∞Pn,2≤3n/5+n/10 in this case.
Case v (n>9andn≡0mod5andn≢0mod10).
In this case, we have an odd number of blocks that were defined in Lemma1. This proof is equivalent to proving that the same distribution in Figure 7 of Case iv can eternally protect Pn,2 against an endless series of attacks taking into consideration the need to assign 4 guards to Bn/5 in order to eternally protect it without the need to summon a guard from another block and that is because Bn/5 does not belong to a pair (we have an odd number of blocks), which explains the need to have one additional guard in this case over Case iv.
Case vi (n≡lmod10andl=1,2,3).
In this case, we have an even number of blocks that were defined in Lemma1. This proof is equivalent to proving that the same distribution in Figure 7 of Case iv can eternally protect Pn,2 against an endless series of attacks with one difference which is placing 1,2,3 additional guards on the additional 2,4,6-vertex subblock when n≡1,2,3mod5, respectively. In each of Figures 9–11 and in a similar way to Case iv, we find a set of configurations of the 7 guards placed on B1,B2 and the additional guards on the subblock SB so that these configurations can cover all the vertices of B1,B2,SB and they are all reachable from each other in one step.
As for the remaining pairs of blocks, we can simply apply the same configurations shown in Figure8 of Case iv. Therefore, the theory holds for all the blocks and we prove the need for 3n/5+n/10+l−1 guards when l=1,2,3.
Case vii (n≡lmod5andn≢lmod10andl=1,2,3).
This case is similar to Case vi with the exception that we need one additional guard onBn/5 because we have an odd number of blocks (similar to Case v).
Case viii (n≡4mod10).
This case is similar to Case vi, with the exception that we can eternally protect the 8-vertex subblockSB with l-2 = 2 guards instead of l-1 guards like in Case vi. Figure 12 shows the distributions of guards in this case.
Case ix (n≡4mod5andn≢4mod10).
This case is similar to Case viii with the exception that we need one additional guard onBn/5 because we have an odd number of blocks (similar to Cases v and vii).
We conclude that the theorem holds for all cases ofn.Figure 6
Eternally dominatingBj with 4 vertices.Figure 7
HP5,2,3.Figure 8
Eternally protectingB1,B2 with 7 guards.Figure 9
Eternally protectingB1,B2,SB with 8 guards.Figure 10
Eternally protectingB1,B2,SB with 9 guards.Figure 11
Eternally protectingB1,B2,SB with 10 guards.Figure 12
Eternally protectingB1,B2,SB with 10 guards.


### 2.3. Eternal Domination Number ofPn,3

In this section, we find the eternal domination number of generalized Petersen graphPn,3 when n≡0mod4 and we give an upper bound for γm∞Pn,3 in the remaining cases: n≡1,2,3mod4.Theorem 3.
γm∞Pn,3=n/2for n≡0mod4.Proof.
Letn=4l:l∈N. From Proposition 3, we know that γPn,3=n/2 for this case and the γ-dominating set S is the union of two sets A and B which are A=v4i+1;0≤i≤l−1, B=u4i+3;0≤i≤l−1. Therefore, according to Propositions 3 and 5, the trivial bounds for γm∞Pn,3 are n/2≤γm∞Pn,3≤n.
We form thek-dominating graph HG,k where G=Pn,3,k=n/2, and with sets
(13)D1=A1∪B1=v4i+1;0≤i≤l−1∪u4i+3;0≤i≤l−1,D2=A2∪B2=v4i+2;0≤i≤l−1∪u4i+4;0≤i≤l−1,D3=A3∪B3=v4i+3;0≤i≤l−1∪u4i+1;0≤i≤l−1,D4=A4∪B4=v4i+4;0≤i≤l−1∪u4i+2;0≤i≤l−1.Each of these setsD1,D2,D3,D4 has a cardinality of n/2 and they are all adjacent in HPn,3,n/2 for the following reasons.D1⟶D2, D2⟶D3, D3⟶D4, D4⟶D1 by rotating the guards of the outer cycle one step clockwise and rotating the guards of the inner cycle one step counterclockwise.D2⟶D1, D3⟶D2, D4⟶D3, D1⟶D4 by rotating the guards on the outer cycle one step counterclockwise and rotating the guards of the inner cycle one step clockwise.D1⟶D3, D3⟶D1, D2⟶D4, D4⟶D2 by reflection which means moving the guards from each cycle one step to occupy the corresponding unoccupied vertex on the other cycle.Therefore,D1,D2,D3,D4 are adjacent in SPn,3,n/2 (the induced subgraph of HPn,3,n/2) on D1,D2,D3,D4 and D1∪D2∪D3∪D4=VPn,3; therefore, we conclude that γm∞Pn,3≤n/2 for n≡0mod4 but γm∞Pn,1≥γPn,1 from the definition of eternal domination, so γm∞Pn,3=γPn,3=n/2 for n≡0mod4; see Figure 13.Figure 13
γm∞P12,3=γP12,3=6.This proof proposes the following idea.Forn≡1,2,3mod4, we can divide VPn,3 into two sets X and Y defined as
(14)X=vi,ui;1≤i≤4l;n≡1,2,3mod4,Y=v4l+1,u4l+1;n≡1mod4,v4l+1,v4l+2,u4l+1,u4l+2;n≡2mod4,v4l+1,v4l+2,v4l+3,u4l+1,u4l+2,u4l+3;n≡3mod4.We notice that any change ofn equals a change in the number of the vertices of X; meanwhile, the number of the vertices of Y does not change. We can use this observation to study the eternal domination problem on Pn,3 when n≡1,2,3mod4, because this observation allows us to take the relationships between the guards situated on the vertices of Y and the end vertices of X of one example “one value of n” then generalize these relationships for any value of n, taking into consideration that the relationships between the guards situated on the inner vertices of X will always be similar to the ones in Theorem 3.Theorem 4.
Forn≥7, we have γm∞Pn,3≤n/2+1;n≡1mod4,n/2+2;n≡2mod4,n/2+2;n≡3mod4.Case 1 (n≥9 and n≡1mod4).
Letn=4l+1:l∈N. From Proposition 3, we know that γPn,3=n/2 for this case and the γ-dominating set S is S=A∪B∪un−1. Therefore, according to Propositions 3 and 5, the trivial bounds for γm∞Pn,3 are n/2≤γm∞Pn,3≤n.We form thek-dominating graph HPn,3,n/2+1 with these sets of cardinalityn/2+1:
(15)D1=v4i+1;0≤i≤l−1∪u4i+3;0≤i≤l−1∪vn,un−1,D2=v4i+2;0≤i≤l−1∪u4i+4;0≤i≤l−1∪vn−1,un,D3=v4i+3;0≤i≤l−1∪u4i+1;0≤i≤l−1∪vn−1,un,D4=v4i+4;0≤i≤l−1∪u4i+2;0≤i≤l−1∪v1,un−2.It is easy to notice thatD1,D2,D3,D4 are all adjacent in HPn,3,n/2+1 and the union D1∪D2∪D3∪D4=VPn,3; therefore, γm∞Pn,3≤n/2+1 for n≡1mod4. See Figure 14.Case 2 (n≥10 and n≡2mod4).
Letn=4l+2:l∈N. From Proposition 3, we know that γPn,3=n/2+1 for this case and the γ-dominating set S is S=A∪B∪vn−1,un−1. Then, according to Propositions 3 and 5, the trivial bounds for γm∞Pn,3 in this case are n/2+1≤γm∞Pn,3≤n.Figure 14
Eternally protectingP13,3 with 8 guards.We form thek-dominating graph HPn,3,n/2+2 with these sets of cardinalityn/2+2:
(16)D1=v4i+1;0≤i≤l−1∪u4i+3;0≤i≤l−1∪vn−2,vn−1,un−1,D2=v4i+2;0≤i≤l−1∪u4i+4;0≤i≤l−1∪vn,un−1,un,D3=v4i+3;0≤i≤l−1∪u4i+1;0≤i≤l−1∪vn−1,vn,un−1,D4=v4i+4;0≤i≤l−1∪u4i+2;0≤i≤l−1∪v1,un−1,un.See Figure15.Case 3 (n≥7 and n≡3mod4).
Letn=4l+3:l∈N. From Proposition 3, we know that γPn,3=n/2+1 for this case and the γ-dominating set S is S=A∪B∪vn−2,un−3,u2. Therefore, according to Propositions 3 and 5, the trivial bounds for γm∞Pn,3 in this specific case are n/2+1≤γm∞Pn,3≤n.Figure 15
Eternally protectingP14,3 with 9 guards.We form thek-dominating graph HPn,3,n/2+2 with these sets of cardinalityn/2+2:
(17)D1=v4i+1;0≤i≤l−1∪u4i+3;0≤i≤l−1∪vn−2,un−2,un−1,un,D2=v4i+2;0≤i≤l−1∪u4i+4;0≤i≤l−1∪vn−2,un−2,un−1,un,D3=v4i+3;0≤i≤l−1∪u4i+1;0≤i≤l−1∪vn−1,un−2,un−1,un,D4=v4i+4;0≤i≤l−1∪u4i+2;0≤i≤l−1∪vn,un−2,un−1,un.It is easy to notice thatD1,D2,D3,D4 are all adjacent in HPn,3,n/2+2 and the union D1∪D2∪D3∪D4=VPn,3; therefore, γm∞Pn,3≤n/2+2 for n≡3mod4. See Figure 16.Figure 16
Eternally protectingP15,3 with 10 guards.From Cases1–3, we conclude the requested.


## 2.1. Eternal Domination Number ofPn,1

In this section, we find them-eternal domination number of Pn,1 for n is arbitrary.Theorem 1.
γm∞Pn,1=n/2forn≡0,1,3mod4,n/2+1forn≡2mod4.Proof.
We consider all four cases ofn.Case 1 (n≡0mod4).
Letn=4l:l∈N. As it was found in [11] that γPn,1=n/2 for this specific case and the γ-dominating set S is the union of two sets A and B which are A=v4i+1;0≤i≤l−1, B=u4i+3;0≤i≤l−1.We form thek-dominating graph HG,k where G=Pn,1, k=n/2, and with sets
(1)D1=A1∪B1=v4i+1;0≤i≤l−1∪u4i+3;0≤i≤l−1,D2=A2∪B2=v4i+2;0≤i≤l−1∪u4i+4;0≤i≤l−1,D3=A3∪B3=v4i+3;0≤i≤l−1∪u4i+1;0≤i≤l−1,D4=A4∪B4=v4i+4;0≤i≤l−1∪u4i+2;0≤i≤l−1.Each of these setsD1,D2,D3,D4 has a cardinality of n/2 and they are adjacent in HPn,1,n/2 for the following reasons.D1⟶D2, D2⟶D3, D3⟶D4, D4⟶D1 by rotating the guards one step clockwise.D2⟶D1, D3⟶D2, D4⟶D3, D1⟶D4 by rotating the guards one step counterclockwise.D1⟶D3, D3⟶D1, D2⟶D4, D4⟶D2 by reflection which means moving the guards one step to occupy the corresponding unoccupied vertex on the other cycle.Therefore,D1,D2,D3,D4 are adjacent in SPn,1,n/2 (the induced subgraph of HPn,1,n/2) on D1,D2,D3,D4 and D1∪D2∪D3∪D4=VPn,1; therefore, we conclude that γm∞Pn,1≤n/2forn≡0mod4 but γm∞Pn,1≥γPn,1 from the definition of eternal domination; therefore, γm∞Pn,1=γPn,1=n/2 for n≡0mod4; see Figure 1.Case 2 (n≡1mod4).
Letn=4l+1:l∈N. It was found in [11] that γPn,1=n/2 for this case and it was found that the γ-dominating set S is S=A∪B∪x:x∈vn,un.Figure 1
γm∞P12,1=γP12,1=6.We form thek-dominating graph HPn,1,n/2 with the following sets of cardinalityn/2:
(2)D1=v4i+1;0≤i≤l−1∪u4i+3;0≤i≤l−1∪vn,D2=v4i+2;0≤i≤l−1∪u4i+4;0≤i≤l−1∪un,D3=v4i+3;0≤i≤l−1∪u4i+1;0≤i≤l−1∪un,D4=v4i+4;0≤i≤l−1∪u4i+2;0≤i≤l−1∪vn.It is easy to notice thatD1,D2,D3,D4 are all adjacent in HPn,1,n/2 and the union D1∪D2∪D3∪D4=VPn,1; therefore, γm∞Pn,1≤n/2 for n≡1mod4 but we have γm∞Pn,1≥γPn,1 from the definition of eternal domination; therefore, γm∞Pn,1=γPn,1=n/2 for n≡1mod4; see Figure 2.Case 3 (n≡2mod4).
Letn=4l+2:l∈N. As it was found in [11], γPn,1=n/2+1 for this specific case and the γ-dominating set S is S=A∪B∪x,y:x,y∈vn−1,vn,un−1,un.Figure 2
γm∞P13,1=γP13,1=7.We form thek-dominating graph HPn,1,n/2+1 with the following sets of the cardinality n/2+1:
(3)D1=v4i+1;0≤i≤l−1∪u4i+3;0≤i≤l−1∪vn−1,un,D2=v4i+2;0≤i≤l−1∪u4i+4;0≤i≤l−1∪vn,un,D3=v4i+3;0≤i≤l−1∪u4i+1;0≤i≤l−1∪vn−1,un−1,D4=v4i+4;0≤i≤l−1∪u4i+2;0≤i≤l−1∪vn,un−1.It is easy to notice thatD1,D2,D3,D4 are all adjacent in HPn,1,n/2+1 and the union of sets D1∪D2∪D3∪D4=VPn,1; therefore, γm∞Pn,1≤n/2+1 for n≡1mod4, γm∞Pn,1≥γPn,1; therefore, γm∞Pn,1=γPn,1=n/2+1; see Figure 3.Case 4 (n≡3mod4).
Letn=4l+3:l∈N. Ebrahimi et al. found in [11] that γPn,1=n/2 for this case and the γ-dominating set S is S=A∪B∪x,y:x,y∈vn−2,vn−1,vn,un−2,un−1,un.Figure 3
γm∞P14,1=γP14,1=8.We form thek-dominating graph HPn,1,n/2 with the following sets of cardinality n/2:
(4)D1=v4i+1;0≤i≤l−1∪u4i+3;0≤i≤l−1∪vn−2,un,D2=v4i+2;0≤i≤l−1∪u4i+4;0≤i≤l−1∪vn−1,un,D3=v4i+3;0≤i≤l−1∪u4i+1;0≤i≤l−1∪un−2,vn,D4=v4i+4;0≤i≤l−1∪u4i+2;0≤i≤l−1∪vn−1,vn.It is easy to notice thatD1,D2,D3,D4 are all adjacent in HPn,1,n/2 and the union D1∪D2∪D3∪D4=VPn,1; therefore, γm∞Pn,1≤n/2 for n≡3mod4 but γm∞Pn,1≥γPn,1; therefore, γm∞Pn,1=γPn,1=n/2 for n≡3mod4; see Figure 4. From Cases 1–4, we conclude that γm∞Pn,1=γPn,1 for n≥3.Figure 4
γm∞P15,1=γP15,1=8.


## 2.2. Eternal Domination Number ofPn,2

In this section, we give an upper bound for the eternal domination number of generalized Petersen graphPn,2.Lemma 1.
If we dividePn,2 into n/5 blocks where each block consists of 10 vertices (5 vertices from the outer cycle and their 5 adjacent vertices from the inner cycle), then 4 guards are enough to eternally dominate each block.Proof.
We denote these blocks byBj:1≤j≤n/5; we also denote the subblock that remains in case n≢0mod5 by SB keeping in mind that SB consists of 2, 4, 6, and 8 vertices when we have n≡1,2,3,4mod5, respectively. It was found in [11] that three vertices are enough to dominate each block Bj if the dominating vertices were distributed as shown in Figure 5.Figure 5
DominatingBj with 3 vertices.To prove that four guards can eternally protect any blockBj it is enough to find a set of configurations for the guards so that these configurations cover all the vertices of Bj (every vertex of Bj belongs to at least one configuration) and every two configurations are reachable from each other in one step; we notice that the configurations presented in Figure 6 can achieve that; therefore, according to the definition of the k-dominating graph, we conclude that γm∞Bj≤4.Theorem 2.
Forn≥5,
(5)γm∞Pn,2=4;nϵ5,6,γm∞P7,2=5,γm∞P8,2∈5,6,γm∞Pn,2≤3n5+n10;n≥9andn≡0mod10,γm∞Pn,2≤3n5+n10;n≥9andn≡0mod5andn≢0mod10,γm∞Pn,2≤3n5+n10+l;n≡lmod10andl=1,2,3,γm∞Pn,2≤3n5+n10+l;n≡lmod5andn≢lmod10andl=1,2,3,γm∞Pn,2≤3n5+n10+2;n≡4mod10,γm∞Pn,2≤3n5+n10+3;n≡4mod5andn≢4mod10.Proof.
We discuss all the cases as follows.
Case i.1 (n=5).
From Propositions2, 4, and 6, we conclude that
(6)3≤γm∞P5,2≤4.
By formingHPn,2,3 (the 3-dominating graph for Pn,2), we notice that VHPn,2,3 consists of the following sets:
(7)D1=v1,u3,u4,D2=v2,u4,u5,D3=v3,u1,u5,D4=v4,u1,u2,D5=v5,u2,u3,D6=v1,v3,u2,D7=v2,v4,u3,D8=v3,v5,u4,D9=v1,v4,u5,D10=v2,v5,u1.
Figure7 illustrates HPn,2,3.
We denote the closed neighborhood of vertexDi in HPn,2,3 by Xi, and we notice the following:
(8)u1∉X1,u2∉X2,u3∉X3,u4∉X4,u5∉X5,v2∉X6,v3∉X7,v4∉X8,v5∉X9,v1∉X10.
Therefore, by the definition ofk-dominating graph, we conclude that γm∞P5,2≠3 which means γm∞P5,2=4 from (6).
We can easily prove that the following family is a 4-vertex eternal dominating family ofP5,2:(9)D1=v1,v2,u4,u5,D2=v4,v5,u1,u2,D3=v1,v3,u3,u4.
Case i.2 (n=6).
From Propositions2, 4, and 6, we conclude that 4≤γm∞P6,2≤4 which means γm∞P6,2=4 and the following family is a 4-vertex eternal dominating family of P6,2:(10)D1=v1,v4,u3,u6,D2=v2,v5,u1,u4,D3=v3,v6,u2,u5.
Case ii (n=7).
From Propositions2, 4, and 6, we conclude that γm∞P7,2=5. The following family is a 5-vertex eternal dominating family of P7,2:
(11)D1=v1,v4,v6,u3,u7,D2=v2,v5,v7,u1,u2,D3=v3,v7,u4,u5,u6.
Case iii (n=8).
From Propositions2, 4, and 6, it can be implied that
(12)5≤γm∞P8,2≤6.
Case iv (n≡0mod10).
In this case, we have an even number of blocks that were defined in Lemma1. For every pair of adjacent blocks, let us assign 3 guards to one of them and 4 guards to the other; we start by studying the first two blocks B1,B2; to prove that the 7 guards assigned to these two blocks are enough to eternally protect them, it is enough to find a set of guard configurations for which every vertex of VB1∪VB2 belongs to at least one of the configurations and every two configurations are reachable from one another in one step. We imply that the configurations shown in Figure 8 satisfy this purpose.
Therefore, the number of guards we assigned toB1,B2 is enough to eternally protect these two blocks. Let us now consider the next attack to occur on a vertex that does not belong to any of these two blocks; for example, the vertex denoted by v18 which is the middle “outer” vertex of B4 and then the guards of B1,B2 return to configuration 1 of Figure 7 and at the same time the guards of B3,B4,B5,B6 move to configuration 3 of Figure 7. It is obvious that these configurations can be applied to all sets of blocks in Pn,2 which means without loss of generality the theory holds and we conclude that γm∞Pn,2≤3n/5+n/10 in this case.
Case v (n>9andn≡0mod5andn≢0mod10).
In this case, we have an odd number of blocks that were defined in Lemma1. This proof is equivalent to proving that the same distribution in Figure 7 of Case iv can eternally protect Pn,2 against an endless series of attacks taking into consideration the need to assign 4 guards to Bn/5 in order to eternally protect it without the need to summon a guard from another block and that is because Bn/5 does not belong to a pair (we have an odd number of blocks), which explains the need to have one additional guard in this case over Case iv.
Case vi (n≡lmod10andl=1,2,3).
In this case, we have an even number of blocks that were defined in Lemma1. This proof is equivalent to proving that the same distribution in Figure 7 of Case iv can eternally protect Pn,2 against an endless series of attacks with one difference which is placing 1,2,3 additional guards on the additional 2,4,6-vertex subblock when n≡1,2,3mod5, respectively. In each of Figures 9–11 and in a similar way to Case iv, we find a set of configurations of the 7 guards placed on B1,B2 and the additional guards on the subblock SB so that these configurations can cover all the vertices of B1,B2,SB and they are all reachable from each other in one step.
As for the remaining pairs of blocks, we can simply apply the same configurations shown in Figure8 of Case iv. Therefore, the theory holds for all the blocks and we prove the need for 3n/5+n/10+l−1 guards when l=1,2,3.
Case vii (n≡lmod5andn≢lmod10andl=1,2,3).
This case is similar to Case vi with the exception that we need one additional guard onBn/5 because we have an odd number of blocks (similar to Case v).
Case viii (n≡4mod10).
This case is similar to Case vi, with the exception that we can eternally protect the 8-vertex subblockSB with l-2 = 2 guards instead of l-1 guards like in Case vi. Figure 12 shows the distributions of guards in this case.
Case ix (n≡4mod5andn≢4mod10).
This case is similar to Case viii with the exception that we need one additional guard onBn/5 because we have an odd number of blocks (similar to Cases v and vii).
We conclude that the theorem holds for all cases ofn.Figure 6
Eternally dominatingBj with 4 vertices.Figure 7
HP5,2,3.Figure 8
Eternally protectingB1,B2 with 7 guards.Figure 9
Eternally protectingB1,B2,SB with 8 guards.Figure 10
Eternally protectingB1,B2,SB with 9 guards.Figure 11
Eternally protectingB1,B2,SB with 10 guards.Figure 12
Eternally protectingB1,B2,SB with 10 guards.


## 2.3. Eternal Domination Number ofPn,3

In this section, we find the eternal domination number of generalized Petersen graphPn,3 when n≡0mod4 and we give an upper bound for γm∞Pn,3 in the remaining cases: n≡1,2,3mod4.Theorem 3.
γm∞Pn,3=n/2for n≡0mod4.Proof.
Letn=4l:l∈N. From Proposition 3, we know that γPn,3=n/2 for this case and the γ-dominating set S is the union of two sets A and B which are A=v4i+1;0≤i≤l−1, B=u4i+3;0≤i≤l−1. Therefore, according to Propositions 3 and 5, the trivial bounds for γm∞Pn,3 are n/2≤γm∞Pn,3≤n.
We form thek-dominating graph HG,k where G=Pn,3,k=n/2, and with sets
(13)D1=A1∪B1=v4i+1;0≤i≤l−1∪u4i+3;0≤i≤l−1,D2=A2∪B2=v4i+2;0≤i≤l−1∪u4i+4;0≤i≤l−1,D3=A3∪B3=v4i+3;0≤i≤l−1∪u4i+1;0≤i≤l−1,D4=A4∪B4=v4i+4;0≤i≤l−1∪u4i+2;0≤i≤l−1.Each of these setsD1,D2,D3,D4 has a cardinality of n/2 and they are all adjacent in HPn,3,n/2 for the following reasons.D1⟶D2, D2⟶D3, D3⟶D4, D4⟶D1 by rotating the guards of the outer cycle one step clockwise and rotating the guards of the inner cycle one step counterclockwise.D2⟶D1, D3⟶D2, D4⟶D3, D1⟶D4 by rotating the guards on the outer cycle one step counterclockwise and rotating the guards of the inner cycle one step clockwise.D1⟶D3, D3⟶D1, D2⟶D4, D4⟶D2 by reflection which means moving the guards from each cycle one step to occupy the corresponding unoccupied vertex on the other cycle.Therefore,D1,D2,D3,D4 are adjacent in SPn,3,n/2 (the induced subgraph of HPn,3,n/2) on D1,D2,D3,D4 and D1∪D2∪D3∪D4=VPn,3; therefore, we conclude that γm∞Pn,3≤n/2 for n≡0mod4 but γm∞Pn,1≥γPn,1 from the definition of eternal domination, so γm∞Pn,3=γPn,3=n/2 for n≡0mod4; see Figure 13.Figure 13
γm∞P12,3=γP12,3=6.This proof proposes the following idea.Forn≡1,2,3mod4, we can divide VPn,3 into two sets X and Y defined as
(14)X=vi,ui;1≤i≤4l;n≡1,2,3mod4,Y=v4l+1,u4l+1;n≡1mod4,v4l+1,v4l+2,u4l+1,u4l+2;n≡2mod4,v4l+1,v4l+2,v4l+3,u4l+1,u4l+2,u4l+3;n≡3mod4.We notice that any change ofn equals a change in the number of the vertices of X; meanwhile, the number of the vertices of Y does not change. We can use this observation to study the eternal domination problem on Pn,3 when n≡1,2,3mod4, because this observation allows us to take the relationships between the guards situated on the vertices of Y and the end vertices of X of one example “one value of n” then generalize these relationships for any value of n, taking into consideration that the relationships between the guards situated on the inner vertices of X will always be similar to the ones in Theorem 3.Theorem 4.
Forn≥7, we have γm∞Pn,3≤n/2+1;n≡1mod4,n/2+2;n≡2mod4,n/2+2;n≡3mod4.Case 1 (n≥9 and n≡1mod4).
Letn=4l+1:l∈N. From Proposition 3, we know that γPn,3=n/2 for this case and the γ-dominating set S is S=A∪B∪un−1. Therefore, according to Propositions 3 and 5, the trivial bounds for γm∞Pn,3 are n/2≤γm∞Pn,3≤n.We form thek-dominating graph HPn,3,n/2+1 with these sets of cardinalityn/2+1:
(15)D1=v4i+1;0≤i≤l−1∪u4i+3;0≤i≤l−1∪vn,un−1,D2=v4i+2;0≤i≤l−1∪u4i+4;0≤i≤l−1∪vn−1,un,D3=v4i+3;0≤i≤l−1∪u4i+1;0≤i≤l−1∪vn−1,un,D4=v4i+4;0≤i≤l−1∪u4i+2;0≤i≤l−1∪v1,un−2.It is easy to notice thatD1,D2,D3,D4 are all adjacent in HPn,3,n/2+1 and the union D1∪D2∪D3∪D4=VPn,3; therefore, γm∞Pn,3≤n/2+1 for n≡1mod4. See Figure 14.Case 2 (n≥10 and n≡2mod4).
Letn=4l+2:l∈N. From Proposition 3, we know that γPn,3=n/2+1 for this case and the γ-dominating set S is S=A∪B∪vn−1,un−1. Then, according to Propositions 3 and 5, the trivial bounds for γm∞Pn,3 in this case are n/2+1≤γm∞Pn,3≤n.Figure 14
Eternally protectingP13,3 with 8 guards.We form thek-dominating graph HPn,3,n/2+2 with these sets of cardinalityn/2+2:
(16)D1=v4i+1;0≤i≤l−1∪u4i+3;0≤i≤l−1∪vn−2,vn−1,un−1,D2=v4i+2;0≤i≤l−1∪u4i+4;0≤i≤l−1∪vn,un−1,un,D3=v4i+3;0≤i≤l−1∪u4i+1;0≤i≤l−1∪vn−1,vn,un−1,D4=v4i+4;0≤i≤l−1∪u4i+2;0≤i≤l−1∪v1,un−1,un.See Figure15.Case 3 (n≥7 and n≡3mod4).
Letn=4l+3:l∈N. From Proposition 3, we know that γPn,3=n/2+1 for this case and the γ-dominating set S is S=A∪B∪vn−2,un−3,u2. Therefore, according to Propositions 3 and 5, the trivial bounds for γm∞Pn,3 in this specific case are n/2+1≤γm∞Pn,3≤n.Figure 15
Eternally protectingP14,3 with 9 guards.We form thek-dominating graph HPn,3,n/2+2 with these sets of cardinalityn/2+2:
(17)D1=v4i+1;0≤i≤l−1∪u4i+3;0≤i≤l−1∪vn−2,un−2,un−1,un,D2=v4i+2;0≤i≤l−1∪u4i+4;0≤i≤l−1∪vn−2,un−2,un−1,un,D3=v4i+3;0≤i≤l−1∪u4i+1;0≤i≤l−1∪vn−1,un−2,un−1,un,D4=v4i+4;0≤i≤l−1∪u4i+2;0≤i≤l−1∪vn,un−2,un−1,un.It is easy to notice thatD1,D2,D3,D4 are all adjacent in HPn,3,n/2+2 and the union D1∪D2∪D3∪D4=VPn,3; therefore, γm∞Pn,3≤n/2+2 for n≡3mod4. See Figure 16.Figure 16
Eternally protectingP15,3 with 10 guards.From Cases1–3, we conclude the requested.



---

*Source: 6627272-2021-01-27.xml*