1. Introduction

In graph protection, mobile agents or guards are placed on vertices in order to defend against a sequence of attacks on a network. See [1] [2] [3] [4] [5] for more background of the graph protection problem. The first idea for eternal domination was introduced by Burger et al. in 2004 [1]. The “all guards move model” or “multiple guards move version” of eternal domination was introduced by Goddard et al. [2]. General bounds of $\gamma \left(G\right)\le {\gamma }_m^{\infty }\left(G\right)\le \alpha \left(G\right)$ were determined in [2], where $\gamma \left(G\right)$ denotes the domination number of G and $\alpha \left(G\right)$ denotes independence number of G. The eternal domination number for cycles $C_n$

and paths $P_n$ was found by Goddard et al. [2] as follows: ${\gamma }_m^{\infty }\left(C_n\right)=\lceil \frac{n}{3}\rceil$ and ${\gamma }_m^{\infty }\left(P_n\right)=\lceil \frac{n}{2}\rceil$. Jahangir Graph $J_{s,m}$ for $m\ge 1$ is a graph on $sm+1$ vertices,

i.e. a graph consisting of a cycle $C_{sm}$ with one additional vertex which is adjacent to m vertices of $C_{sm}$ at distance s from each other on $C_{sm}$ see [6] for more information on Jahangir graph. Let $v_{sm+1}$ be the label of the central vertex and $v_1,v_2,\cdots ,v_{sm}$ be the labels of the vertices that incident clockwise on cycle $C_{2m}$ so that $\mathrm{deg}\left(v_1\right)=3$. We will use this labeling for the rest of the paper. The vertices that are adjacent to $v_{sm+1}$ have the labels $v_1,v_{1+s},v_{1+2s},\cdots ,v_{1+\left(m-1\right)s}$. We denote the set $\left\{v_1,v_{1+s},\cdots ,v_{1+\left(m-1\right)s}\right\}$ by R. So, $R=\left\{v_{1+is}:i=0,1,\cdots ,m-1\right\}$. By definition, for $s=1$, Jahangir Graph $J_{1,m}$ is the wheel graph $W_m$ and it was mentioned in [6] that ${\gamma }_m^{\infty }\left(W_m\right)=2$ for $m\ge 3$. The k-dominating graph $H\left(G,k\right)$ was defined by Goldwasser et al. [7] as follows: Let G be a graph with a dominating set of cardinality k. The vertex set of the k-dominating graph $H\left(G,k\right)$, denoted $V\left(H\right)$, is the set of all subsets of $V\left(G\right)$ 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, ${\gamma }_m^{\infty }\left(G\right)\le k$ if and only if $H\left(G,k\right)$ has an induced subgraph $S\left(G,k\right)$ such that for each vertex x of $S\left(G,k\right)$, the union of the vertices in the closed neighborhood of x in $S\left(G,k\right)$ is equal to $V\left(G\right)$.

Proposition 1.1 [6] : $\gamma \left(J_{2,m}\right)=\lceil \frac{m}{2}\rceil +1$ for $m\ge 4$.

2. Main Results

Eternal Domination Number of $J_{2,m}$

In this section, we give the exact eternal domination number of $J_{2,m}$.

Lemma 2.1: Let us have a graph $J_{2,m}$. For $m>6$ when m is even and $m>9$

when m is odd, then a set $S\subset V\left(J_{2,m}\right)$ of cardinality $\left|S\right|=\lceil \frac{m}{2}\rceil +1$ can’t dominate $J_{2,m}$ if $v_{2m+1}\notin S$.

Proof: Since $v_{2m+1}\notin S$ that means all the vertices of S are vertices from the

outer cycle $C_{2m}$. We know that $\gamma \left(C_{2m}\right)=\lceil \frac{2m}{3}\rceil$. So let’s find out the values of m for which: $\lceil \frac{2m}{3}\rceil >\lceil \frac{m}{2}\rceil +1$. This arbitrator is true for m is even with $m>6$ and for m is odd with $m>9$. ■

Theorem 2.1. ${\gamma }_m^{\infty }\left(J_{2,m}\right)=\{\begin{array}{l}\gamma \left(J_{2,m}\right)+1:m=3,\\ \gamma \left(J_{2,m}\right):m\in \left\{2,4,5,6,7,9\right\}.\end{array}$

Proof: We know from the definition of eternal domination that

$\gamma \left(J_{2,m}\right)\le {\gamma }_m^{\infty }\left(J_{2,m}\right)$.

Therefore from proposition 1.1, we have $\lceil \frac{m}{2}\rceil +1\le {\gamma }_m^{\infty }\left(J_{2,m}\right)$ for $m\ge 4$. This

means we only need to prove that ${\gamma }_m^{\infty }\left(J_{2,m}\right)\le \gamma \left(J_{2,m}\right)$ for $m\in \left\{2,4,5,6,7,9\right\}$. In order to do that we form the k-dominating graph $H\left(J,k\right)$ on graph $J_{2,m}$ with $k=\gamma \left(J_{2,m}\right)$ and $m\in \left\{2,4,5,6,7,9\right\}$. We consider the following cases:

Case 1. $m=3$: It was found in [3] that $\gamma \left(J_{2,3}\right)=2$. Therefore ${\gamma }_m^{\infty }\left(J_{2,3}\right)\ge 2$. However, it is obvious that two vertices can dominate $J_{2,3}$ if and only if both vertices belong to the outer cycle $C_6$. Therefore if the central vertex $v_7$ is attacked, then one of the two guards that are located on the two dominating vertices would have to move to $v_7$ making it impossible for the new distribution of guards to dominate the entire graph because $v_7$ doesn’t belong to any of the 2-dominating sets of $J_{2,3}$. Therefore ${\gamma }_m^{\infty }\left(J_{2,3}\right)>2$. We form $H\left(J_{2,3},3\right)$, the 3-dominating graph on $J_{2,3}$. Let $S\left(J_{2,3},3\right)$ be the induced subgraph of $H\left(J_{2,3},3\right)$ on vertices: $D_1=\left\{v_1,v_4,v_7\right\}$, $D_2=\left\{v_2,v_5,v_7\right\}$, $D_3=\left\{v_3,v_6,v_7\right\}$. Since $D_1,D_2,D_3$ are all adjacent and $D_1\cup D_2\cup D_3=V\left(J_{2,3}\right)$, therefore we have ${\gamma }_m^{\infty }\left(J_{2,3}\right)\le 3$, which means $2<{\gamma }_m^{\infty }\left(J_{2,3}\right)\le 3$, therefore ${\gamma }_m^{\infty }\left(J_{2,3}\right)=3$.

Case 2. $m=2$: We have $k=\gamma \left(J_{2,2}\right)=2$. Let’s form $S\left(J_{2,2},2\right)$ to be the induced subgraph of $H\left(J_{2,2},2\right)$ on vertices $D_1=\left\{v_1,v_5\right\}$, $D_2=\left\{v_2,v_3\right\}$, $D_3=\left\{v_3,v_4\right\}$. Since $D_1,D_2,D_3$ are adjacent and $D_1\cup D_2\cup D_3=V\left(J_{2,2}\right)$ therefore we have

${\gamma }_m^{\infty }\left(J_{2,2}\right)\le \lceil \frac{m}{2}\rceil +1=2$ which means ${\gamma }_m^{\infty }\left(J_{2,2}\right)=\lceil \frac{m}{2}\rceil +1=2$.

Case 3. $m=4$: We have $k=\lceil \frac{m}{2}\rceil +1=3$. Let’s form $S\left(J_{2,4},3\right)$ to be the

induced subgraph of $H\left(J_{2,4},3\right)$ on the following vertices: $D_1=\left\{v_3,v_7,v_9\right\}$, $D_2=\left\{v_1,v_4,v_7\right\}$, $D_3=\left\{v_1,v_3,v_6\right\}$, $D_4=\left\{v_2,v_5,v_8\right\}$. Since $D_1,D_2,D_3,D_4$ are all adjacent and $D_1\cup D_2\cup D_3\cup D_4=V\left(J_{2,4}\right)$, therefore

${\gamma }_m^{\infty }\left(J_{2,4}\right)\le \lceil \frac{m}{2}\rceil +1=3$ which means ${\gamma }_m^{\infty }\left(J_{2,4}\right)=\lceil \frac{m}{2}\rceil +1=3$.

Case 4. $m=5$: We have $k=\lceil \frac{m}{2}\rceil +1=4$. Let’s form $S\left(J_{2,5},4\right)$ to be the

induced subgraph of $H\left(J_{2,5},4\right)$ on the following vertices: $D_1=\left\{v_1,v_4,v_7,v_9\right\}$, $D_2=\left\{v_2,v_5,v_7,v_{10}\right\}$, $D_3=\left\{v_3,v_6,v_8,v_{10}\right\}$, $D_4=\left\{v_1,v_5,v_9,v_{11}\right\}$. Since $D_1,D_2,D_3,D_4$ are all adjacent and $D_1\cup D_2\cup D_3\cup D_4=V\left(J_{2,5}\right)$ therefore

${\gamma }_m^{\infty }\left(J_{2,5}\right)\le \lceil \frac{m}{2}\rceil +1=4$ which means ${\gamma }_m^{\infty }\left(J_{2,5}\right)=\lceil \frac{m}{2}\rceil +1=4$.

Case 5. $m=6$: We have $k=\lceil \frac{m}{2}\rceil +1=4$. Let’s form $S\left(J_{2,6},4\right)$ to be the

induced subgraph of $H\left(J_{2,5},4\right)$ on these vertices: $D_1=\left\{v_1,v_4,v_7,v_{10}\right\}$, $D_2=\left\{v_2,v_5,v_8,v_{11}\right\}$, $D_3=\left\{v_3,v_6,v_9,v_{12}\right\}$, $D_4=\left\{v_1,v_5,v_9,v_{13}\right\}$. Since $D_1,D_2,D_3,D_4$ are adjacent and $D_1\cup D_2\cup D_3\cup D_4=V\left(J_{2,6}\right)$, therefore

${\gamma }_m^{\infty }\left(J_{2,6}\right)\le \lceil \frac{m}{2}\rceil +1=4$ which means ${\gamma }_m^{\infty }\left(J_{2,6}\right)=\lceil \frac{m}{2}\rceil +1=4$.

Case 6. $m=7$: We have $k=\lceil \frac{m}{2}\rceil +1=5$. Let’s form $S\left(J_{2,7},5\right)$ to be the induced subgraph of $H\left(J_{2,7},5\right)$ on the following vertices: $D_1=\left\{v_1,v_4,v_7,v_{10},v_{13}\right\}$, $D_2=\left\{v_2,v_5,v_8,v_{11},v_{14}\right\}$, $D_3=\left\{v_1,v_3,v_6,v_9,v_{12}\right\}$, $D_4=\left\{v_1,v_3,v_9,v_{13},v_{15}\right\}$. Since $D_1,D_2,D_3,D_4$ are adjacent and $D_1\cup D_2\cup D_3\cup D_4=V\left(J_{2,7}\right)$, therefore

${\gamma }_m^{\infty }\left(J_{2,7}\right)\le \lceil \frac{m}{2}\rceil +1=5$ which means ${\gamma }_m^{\infty }\left(J_{2,7}\right)=\lceil \frac{m}{2}\rceil +1=5$.

Case 7. $m=9$: We have $k=\lceil \frac{m}{2}\rceil +1=6$. Let’s form $S\left(J_{2,9},6\right)$ to be the

induced subgraph of $H\left(J_{2,9},6\right)$ on the vertices: $D_1=\left\{v_1,v_4,v_7,v_{10},v_{13},v_{16}\right\}$, $D_2=\left\{v_2,v_5,v_8,v_{11},v_{14},v_{17}\right\}$, $D_3=\left\{v_3,v_6,v_9,v_{12},v_{15},v_{18}\right\}$, $D_4=\left\{v_2,v_5,v_9,v_{13},v_{17},v_{19}\right\}$. Since $D_1,D_2,D_3,D_4$ are all adjacent and $D_1\cup D_2\cup D_3\cup D_4=V\left(J_{2,9}\right)$, therefore

${\gamma }_m^{\infty }\left(J_{2,9}\right)\le \lceil \frac{m}{2}\rceil +1=6$ which means ${\gamma }_m^{\infty }\left(J_{2,9}\right)=\lceil \frac{m}{2}\rceil +1=6$.

(See Figure 1 for $J_{2,9}$ ). ■

Lemma 2.2: ${\gamma }_m^{\infty }\left(J_{2,m}\right)>\lceil \frac{m}{2}\rceil +1$ for $m\ge 8$ and $m\ne 9$.

Proof: From the definition of eternal domination, we already know that

${\gamma }_m^{\infty }\left(G\right)\ge \gamma \left(G\right)$. By proposition 1.1, $\gamma \left(J_{2,m}\right)=\lceil \frac{m}{2}\rceil +1$ for $m\ge 4$. We just need to prove that ${\gamma }_m^{\infty }\left(J_{2,m}\right)\ne \lceil \frac{m}{2}\rceil +1$ for $m\ge 8$ and $m\ne 9$. We consider both cases:

Case 1: m is even for $m\ge 8$.

In this case the sets

$S_0=\left\{v_1,v_5,\cdots ,v_{2m-3},v_{2m+1}\right\}$ and $B_0=\left\{v_3,v_7,\cdots ,v_{2m-1},v_{2m+1}\right\}$

are the only two minimum dominating sets (γ-dominating set) of $J_{2,m}$ where both $S_0$ and $B_0$ are similar by symmetry. We study an arbitrary attack on a vertex $v_i$ from a graph $J_{2,m}$ protected by $S_0$ and we prove that $S_0$ fails to eternally protect $J_{2,m}$. Let the attacked vertex $v_i$ have an odd (index) label, $v_i\in \left\{v_3,v_7,\cdots ,v_{2m-1}\right\}$. The only guard protecting $v_i$ in this case is the guard occupying the central vertex $v_{2m+1}$ (which is adjacent to all the odd vertices of $C_{2m}$ ). This means the guard on $v_{2m+1}$ has to move to $v_i$ to defend the attack. However, that would leave the vertices: $\left\{v_3,v_7,\cdots ,v_{i-4},v_{i+4},\cdots ,v_{2m-1}\right\}$ unprotected. To try to avoid that we have two strategies:

Strategy 1: We move another guard (occupying an odd vertex $v_j\in S_0$: $v_j\ne v_i$ ) to $v_{2m+1}$ to keep $\left\{v_3,v_7,\cdots ,v_{i-4},v_{i+4},\cdots ,v_{2m-1}\right\}$ protected. However, that would leave at least one of the two vertices $v_{j-1},v_{j+1}$ unprotected and this strategy fails, see Figure 2.

Strategy 2: We don’t move any other guard to $v_{2m+1}$ which would leave

$\lceil \frac{m}{2}\rceil +1$ guards on the vertices of cycle $C_{2m}$ to protect $J_{2,m}$. By Lemma 2.1

these guards can’t protect $J_{2,m}$ if $m>6$ therefore this strategy fails as well, see Figure 3.

Since both of these strategies fail then ${\gamma }_m^{\infty }\left(J_{2,m}\right)>\lceil \frac{m}{2}\rceil +1$ for $m\ge 8$ &

$m\equiv 0\left(\mathrm{mod}2\right)$. Without loss of generality, the same argument can be followed to

prove that $\lceil \frac{m}{2}\rceil +1$ guards can’t eternally protect $J_{2,m}$ in case the minimum dominating set is $B_0$.

Case 2: m is odd for $m>9$.

In this case the minimum dominating sets (γ-dominating sets) of $J_{2,m}$ are:

$U_0=\left\{v_1,v_5,\cdots ,v_{2m-5},v_{2m-3},v_{2m+1}\right\},$

$U_1=\left\{v_1,v_5,\cdots ,v_{2m-5},v_{2m-2},v_{2m+1}\right\},$

$U_2=\left\{v_1,v_5,\cdots ,v_{2m-5},v_{2m-1},v_{2m+1}\right\},$

$U_3=\left\{v_3,v_7,\cdots ,v_{2m-3},v_{2m-1},v_{2m+1}\right\},$

$U_4=\left\{v_3,v_7,\cdots ,v_{2m-3},v_{2m},v_{2m+1}\right\},$

$U_5=\left\{v_1,v_5,\cdots ,v_{2m-5},v_{2m},v_{2m+1}\right\}.$

We study an arbitrary attack on a vertex $v_i$ from three cases of $J_{2,m}$ protected by $U_0,U_1,U_2$ of $J_{2,m}$ respectively. We prove that $U_0,U_1,U_2$ fail to eternally protect these graphs. Let the attacked vertex $v_i$ have an odd (index) label, $v_i\in \left\{v_3,v_7,\cdots ,v_{2m-5}\right\}$. The only guard protecting $v_i$ in this case is the guard occupying the central vertex $v_{2m+1}$ (which is adjacent to all the odd vertices of $C_{2m}$ ). This means the guard on $v_{2m+1}$ has to move to $v_i$ to defend the attack. However, that would leave the vertices: $\left\{v_3,v_7,\cdots ,v_{i-4},v_{i+4},\cdots \right\}$ unprotected. To try to avoid that we have two strategies:

Strategy 1: We move another guard (occupying an odd vertex $v_j\in S_0$ ) to vertex $v_{2m+1}$ to keep $\left\{v_3,v_7,\cdots ,v_{i-4},v_{i+4},\cdots \right\}$ protected. However, that would leave at least one of the two neighboring vertices to $v_j$ $\left(v_{j-1},v_{j+1}\right)$ unprotected therefore this strategy fails, see Figure 4.

Strategy 2: We don’t move any other guard to $v_{2m+1}$ which would leave $\left[\frac{m}{2}\right]+1$ guards on the vertices of cycle $C_{2m}$ to protect $J_{2,m}$. By Lemma 2.1 these guards can’t protect $J_{2,m}$ if $m>9$, therefore this strategy fails as well, see Figure 5.

Since both strategies fail then ${\gamma }_m^{\infty }\left(J_{2,m}\right)>\lceil \frac{m}{2}\rceil +1$ for m is odd and $m>9$.

Without loss of generality, the same argument can be followed to prove that

$\lceil \frac{m}{2}\rceil +1$ guards cannot eternally protect $J_{2,m}$ in case the minimum dominating set is $U_3,U_4$ or $U_5$. From cases 1 and 2 we conclude that:

${\gamma }_m^{\infty }\left(J_{2,m}\right)\ne \lceil \frac{m}{2}\rceil +1$ for $m\ge 8$ and $m\ne 9$.

However, we know ${\gamma }_m^{\infty }\left(J_{2,m}\right)\ge \gamma \left(J_{2,m}\right)=\lceil \frac{m}{2}\rceil +1$ for $m\ge 4$, therefore:

${\gamma }_m^{\infty }\left(J_{2,m}\right)>\lceil \frac{m}{2}\rceil +1$ for $m\ge 8$ and $m\ne 9$. ■

Theorem 2.2: ${\gamma }_m^{\infty }\left(J_{2,m}\right)=\lceil \frac{m}{2}\rceil +2$ for $m\ge 8$ and $m\ne 9$.

Proof: From Lemma 2.2 It is enough to prove the existence of one eternal

dominating family of the vertices of $J_{2,m}$ with cardinality $\lceil \frac{m}{2}\rceil +2$ in order to prove that ${\gamma }_m^{\infty }\left(J_{2,m}\right)=\lceil \frac{m}{2}\rceil +2$. We consider both cases:

Case a. m is even:

We start by forming the k-dominating graph denoted $H\left(G,k\right)$ on $J_{2,m}$ with

$k=\lceil \frac{m}{2}\rceil +2$. $S_0=\left\{v_1,v_5,\cdots ,v_{2m-3},v_{2m+1}\right\}$ is a dominating set of $J_{2,m}$. We form

Y the family of dominating sets as follows $=\left\{D_j\right\}=\left\{S_0\cup \left\{v_j\right\}\right\}$: $v_j\in V\left(J_{2,m}\right)-S_0$. Hence the cardinality of $D_j$ is $\lceil \frac{m}{2}\rceil +2$. Therefore each set of the family Y is a vertex of $H\left(J_{2,m},\lceil \frac{m}{2}\rceil +2\right)$. It is obvious that the union of these vertices is $V\left(J_{2,m}\right)$. We now need to prove that these vertices are all adjacent in $H\left(J_{2,m},\lceil \frac{m}{2}\rceil +2\right)$. There are two types of sets $D_j$ depending on the label of the vertex $v_j$:

Type 1:

$O=\left\{S_0\cup \left\{v_j\right\}:v_j\in M=\left\{v_3,v_7,\cdots ,v_{2m-1}\right\}\text{and}{v}_j\text{isanoddvertexof}{C}_{2m}\right\}$.

Type 2:

$Q=\left\{S_0\cup \left\{v_j\right\}:v_j\in E=\left\{v_2,v_4,\cdots ,v_{2m}\right\}\text{and}{v}_j\text{isanevenvertexof}{C}_{2m}\right\}$.

When an arbitrary unoccupied vertex $v_i\in V\left(J_{2,m}\right)$ is attacked we consider the following cases:

Case a.1. $v_j\in M=\left\{v_3,v_7,\cdots ,v_{2m-1}\right\}$: we consider the following cases:

Case a.1.1. $v_i$ is an unoccupied odd vertex $\left(v_i\in M=\left\{v_3,v_7,\cdots ,v_{2m-1}\right\}\right)$: In this case the guard on the central vertex $v_{2m+1}$ moves to $v_i$ to defend the attack and the guard on $v_j\in M$ moves to $v_{2m+1}$ to protect the remaining odd vertices without disturbing the protection of the even vertices (which are protected by the

guards on the vertices of $S_0$ ) (see Figure 6), which means $\lceil \frac{m}{2}\rceil +2$ guards are

enough to protect $J_{2,m}$ in this case. After defending the attack and since $v_i\in M$ the resulting dominating set $D_i\in O$. We will now use the same argument to prove the results for all cases of $v_i,v_j$ when m is even, taking into consideration that the same path can be followed to prove all the possible cases of $v_i,v_j$ when m is odd.

Case a.1.2. $v_i$ is an even vertex $\left(v_i\in E=\left\{v_2,v_4,\cdots ,v_{2m}\right\}\right)$: In this case the neighboring odd vertex has the only available guard to defend $v_i$. So the guard on $v_{i+1}$ (or $v_{i-1}$ ) moves to $v_i$ to defend the attack leaving $v_{i+2}$ (or $v_{i-2}$ ) respectively unprotected, so the guard on $v_{2m+1}$ moves to $v_{i+1}$ (or $v_{i-1}$ ) respectively, and the guard on $v_j\in M$ moves to $v_{2m+1}$ to protect the remaining vertices of M. While the guards on the vertices of the set $S_0$ keep protecting those vertices and the even vertices of $C_{2m}$ leaving $J_{2,m}$ protected, see Figure 7.

After defending the attack and since $v_i\in E$ the resulting dominating set $D_i\in Q$.

Case a.2: $v_j\in E=\left\{v_2,v_4,\cdots ,v_{2m}\right\}$, we consider the following cases:

Case a.2.1: $v_i$ is an unoccupied odd vertex $\left(v_i\in M=\left\{v_3,v_7,\cdots ,v_{2m-1}\right\}\right)$. In this case the guard on $v_{2m+1}$ moves to $v_i$, either $v_{j+1}$ or $v_{j-1}\in S_0$. So the guard on $v_{j+1}$ (or $v_{j-1}$ ) moves to $v_{2m+1}$ and the guard on $v_j$ moves to $v_{j+1}$ (or $v_{j-1}$ ) respectively, keeping the entire graph protected. After defending the attack and since $v_i\in M$ the resulting dominating set $D_i\in O$. Figure 8, illustrates the

process in which $\lceil \frac{m}{2}\rceil +2=6$ guards can successfully defend $J_{2,8}$ when the

attacked vertex $v_i$ has an odd index label ( $v_3$ ) while the additional guard besides $S_0$ has an even index label ( $v_{10}$ ).

Case a.2.2: $v_i$ is an even index vertex $\left(v_i\in E=\left\{v_2,v_4,\cdots ,v_{2m}\right\}\right)$: In this case $v_{i+1}\left(\text{or}{v}_{i-1}\right)\in S_0$, so the guard on $v_{i+1}$ (or $v_{i-1}$ ) moves to $v_i$. The guard on $v_{2m+1}$ moves to $v_{i+1}$ (or $v_{i-1}$ ) respectively. The guard on $v_{j+1}$ (or $v_{j-1}$ ) moves to $v_{2m+1}$ and the guard on $v_j$ moves to $v_{j+1}$ (or $v_{j-1}$ ) respectively leaving the graph $J_{2,m}$ fully protected, see Figure 9.

After defending the attack and since $v_i\in E$ the resulting dominating set $D_i\in Q$.

After discussing all possible cases we find that for any $D_i,D_k\in Y$: $D_i,D_k$ are

adjacent in $H\left(J_{2,m},\lceil \frac{m}{2}\rceil +2\right)$ because the guards occupying $D_i$ can move to occupy $D_k$ in one move and vice versa. Therefore we form $S\left(J_{2,m},\lceil \frac{m}{2}\rceil +2\right)$ on

the vertices $\left\{\left\{D_j\right\}=\left\{S_0\cup \left\{v_j\right\}\right\}\right\}$, therefore these vertices are adjacent in the induced subgraph $S\left(J_{2,m},k\right)$. It is obvious that ${\displaystyle {\cup }_j\left(D_j\right)}=V\left(J_{2,m}\right)$, therefore

${\gamma }_m^{\infty }\left(J_{2,m}\right)\le \lceil \frac{m}{2}\rceil +2$ for m is even and $m\ge 8$. However, from Lemma 2.2 ${\gamma }_m^{\infty }\left(J_{2,m}\right)>\lceil \frac{m}{2}\rceil +1$. Therefore ${\gamma }_m^{\infty }\left(J_{2,m}\right)=\lceil \frac{m}{2}\rceil +2$ for m is even and $m\ge 8$.

Case b. m is odd and $m>9$:

We begin by forming the k-dominating graph $H\left(G,k\right)$ on $J_{2,m}$ with

$k=\lceil \frac{m}{2}\rceil +2$. $U_0=\left\{v_1,v_5,\cdots ,v_{2m-5},v_{2m-3},v_{2m+1}\right\}$ is a dominating set of $J_{2,m}$. We

form Y the family of dominating sets $Y=\left\{D_j\right\}=\left\{U_0\cup \left\{v_j\right\}\right\}$: $v_j\in V\left(J_{2,m}\right)-U_0$.

Hence the cardinality of $D_j$ is $\lceil \frac{m}{2}\rceil +2$. Therefore each set of the family Y is a vertex of $H\left(J_{2,m},\lceil \frac{m}{2}\rceil +2\right)$. It is obvious that the union of these vertices is $V\left(J_{2,m}\right)$. We now need to prove that these vertices are all adjacent in $H\left(J_{2,m},\lceil \frac{m}{2}\rceil +2\right)$.

There are two types of $D_j$ dependeng on the label of the vertex $v_j$:

Type 1: O = { $U_0\cup \left\{v_j\right\}$ where $v_j\in M=\left\{v_3,v_7,\cdots ,v_{2m-7},v_{2m-1}\right\}$ and $v_j$ is an unoccupied odd vertex of $C_{2m}$ }.

Type 2: Q = { $U_0\cup \left\{v_j\right\}$ where $v_j\in E=\left\{v_2,v_4,\cdots ,v_{2m}\right\}$ and $v_j$ is an even vertex of $C_{2m}$ }.

By following the same argument that we followed in case a, we conclude that:

${\gamma }_m^{\infty }\left(J_{2,m}\right)=\lceil \frac{m}{2}\rceil +2$ for m is odd and $m>9$.

From case a and case b we conclude that:

${\gamma }_m^{\infty }\left(J_{2,m}\right)=\lceil \frac{m}{2}\rceil +2$ for $m\ge 8$ and $m\ne 9$. ■

3. Domination and Eternal Domination Numbers of $J_{3,m}$

In this section we consider the graph $J_{3,m}$. So, we found the exact domination and eternal domination numbers of $J_{3,m}$.

Theorem 3.1: $\gamma \left(J_{3,m}\right)=m$ for $m\ge 2$ and the γ-dominating set is unique.

Proof: For $J_{3,m}$, let $R=\left\{v_{1+3i}:i=0,1,\cdots ,m-1\right\}=\left\{v_1,v_4,\cdots ,v_{3m-2}\right\}$. Since $V\left(C_{3m}\right)=3m$ it is easy to verify that the set of vertices $S_0=\left\{v_1,v_4,\cdots ,v_{3m-2}\right\}$ is a dominating set of cardinality m for $J_{3,m}$. Therefore $\gamma \left(J_{3,m}\right)\le m$ for $m\ge 2$. Let $D_0\subset V\left(J_{3,m}\right)$ such that $\left|D_0\right|=m-1$ and $D_0$ is a dominating set of $J_{3,m}$. We consider the following cases:

Case a: Let $v_{3m+1}\in D_0$ then the vertex $v_{3m+1}$ clearly dominates m vertices of the cycle $C_{3m}$, which leaves the remaining $m-2$ guards in the set $D_0-\left\{v_{3m+1}\right\}$ to dominate the remaining 2m vertices of cycle $C_{3m}$.

$T_1=\left\{v_2,v_3\right\},T_2=\left\{v_5,v_6\right\},\cdots ,T_m=\left\{v_{3m-1},v_{3m}\right\}$

are m subsets of cardinality 2, each consists of two non-dominated vertices of $C_{3m}$. In order to dominate each of these subsets we need a vertex $x\in D_0$, which means we need at least m vertices to dominate these remaining vertices. Therefore since $\left|D_0\right|=m-1$, there are at least four vertices of $V\left(J_{3,m}\right)$ that no vertices of $D_0$ can dominate which is a contradiction.

Case b: $v_{3m+1}\notin D_0$. In this case $D_0$ is a dominating set of $m-1$ vertices that

dominates a cycle $C_{3m}$ which creates a contradiction since $\gamma \left(C_{3m}\right)=\lceil \frac{3m}{3}\rceil =m$.

Therefore, $\gamma \left(J_{3,m}\right)=m$. Finally, by case a and case b we conclude that $S_0$ is the unique dominating set of cardinality m for $J_{3,m}$. ■

Lemma 3.2: ${\gamma }_m^{\infty }\left(J_{3,m}\right)>m$ for $m\ge 2$.

Proof: In Theorem 3.1, we found that $\gamma \left(J_{3,m}\right)=m$. Since ${\gamma }_m^{\infty }\left(G\right)\ge \gamma \left(G\right)$, we conclude that ${\gamma }_m^{\infty }\left(J_{3,m}\right)\ge m$. Let $S_0=\left\{v_1,v_4,\cdots ,v_{3m-2}\right\}$ be the m-dominating set of $J_{3,m}$ and let’s assume that each vertex of $S_0$ is occupied by a guard. When an unoccupied vertex $v\in V\left(J_{3,m}\right)-S_0$ is attacked we consider the following cases:

Case a. The attacked vertex $v_i\in V\left(C_{3m}\right)-S_0$: In this case the only guard that can move to $v_i$ to defend the attack is $v_{i+1}$ or $v_{i-1}$ because $v_{3m+1}\notin S_0$.

Case a.1: If the guard is situated on $v_{i+1}$ then it moves to $v_i$ to defend the attack. Therefore all the guards of the exterior cycle $C_{3m}$ should move one edge (counter clockwise) to keep the cycle protected making the new dominating set $S_2=\left\{v_3,v_6,\cdots ,v_{3m-3},v_{3m}\right\}$. However, according to Theorem 3.1 the vertex $v_{3m+1}$ won’t be protected anymore, see Figure 10.

Case a.2: If the guard is situated on $v_{i-1}$ then it moves to $v_i$ and all the guards on the vertices of $C_{3m}$ should move one edge clockwise to keep the cycle $C_{3m}$ protected making the new dominating set $S_1=\left\{v_2,v_5,\cdots ,v_{3m-1}\right\}$. However, according to Theorem 3.1 the vertex $v_{3m+1}$ won’t be protected anymore, see Figure 11.

Case b: The attacked vertex $v_i$ is $v_{3m+1}$. In this case, there are m guards on the vertices of $S_0=\left\{v_1,v_4,\cdots ,v_{3m-2}\right\}$ each one qualifies to move to $v_{3m+1}$. Let $v_j\in S_0$ have the guard that moves to $v_{3m+1}$. This leaves the two vertices $v_{j-1},v_{j+1}$ unprotected and there are no available guards on the cycle $C_{3m}$ to protect them without leaving gaps of unprotected vertices. From cases a and b we conclude that ${\gamma }_m^{\infty }\left(J_{3,m}\right)>m$. Hence ${\gamma }_m^{\infty }\left(J_{3,m}\right)\ge m+1$. ■

Theorem 3.3: ${\gamma }_m^{\infty }\left(J_{3,m}\right)=m+1$ for $m\ge 2$.

Proof: We form the $H\left(J_{3,m},k\right)$ (k-dominating Graph) on $J_{3,m}$ with $k=m+1$. Let the dominating sets $\left\{D_1,D_2,D_3\right\}$ be defined as follows:

$D_1=S_0\cup \left\{v_{3m+1}\right\}=\left\{v_1,v_4,\cdots ,v_{3m-2},v_{3m+1}\right\},$

$D_2=S_1\cup \left\{v_{3m+1}\right\}=\left\{v_2,v_5,\cdots ,v_{3m-1},v_{3m+1}\right\},$

$D_3=S_2\cup \left\{v_{3m+1}\right\}=\left\{v_3,v_6,\cdots ,v_{3m},v_{3m+1}\right\}.$

Each of $D_1,D_2,D_3$ is a dominating set of the cardinality $m+1$ for $J_{3,m}$ therefore they are vertices of $H\left(J_{3,m},m+1\right)$ and they are all adjacent in $H\left(J_{3,m},m+1\right)$ because they are reachable from each other in one step only. With the guard on the central vertex $v_{3m+1}$ staying in place, the dominating sets $D_1,D_2,D_3$ can result from each other as follows:

$D_1\stackrel{\text{clockwise}}{\Rightarrow }{D}_2,D_2\stackrel{\text{clockwise}}{\Rightarrow }{D}_3,D_3\stackrel{\text{clockwise}}{\Rightarrow }{D}_1,$

$D_1\stackrel{\text{counter-clockwise}}{\Rightarrow }{D}_3,D_2\stackrel{\text{counter-clockwise}}{\Rightarrow }{D}_1,D_3\stackrel{\text{counter-clockwise}}{\Rightarrow }{D}_2$

We form $S\left(J_{3,m},m+1\right)$ the induced subgraph from $H\left(J_{3,m},m+1\right)$ on the previous vertices $D_1,D_2,D_3$. Since $D_1\cup D_2\cup D_3=V\left(J_{3,m}\right)$ then ${\gamma }_m^{\infty }\left(J_{3,m}\right)\le k=m+1$.

Now, by last results together with Lemma 3.2 that $m+1\le {\gamma }_m^{\infty }\left(J_{3,m}\right)\le m+1$. Therefore ${\gamma }_m^{\infty }\left(J_{3,m}\right)=m+1$. See Figure 12. ■

4. Conclusion

In this paper, we studied the eternal domination number of Jahangir graph $J_{s,m}$ for =2, 3 and arbitrary m. We also find the domination number for $J_{3,m}$. By using the same approach, we will work to find the eternal domination number of Jahangir graph $J_{s,m}$ for arbitraries s and m.