Domination and Eternal Domination of Jahangir Graph

Show more

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

Figure 1. ${J}_{2,9}$.

Figure 2. Illustrating strategy 1 when m = 8.

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\},$

Figure 3. Illustrating strategy 2 when m = 8.

${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$. ■

Figure 4. For Strategy 1 on ${J}_{2,13}$.

Figure 5. For Strategy 2 on ${J}_{2,13}$.

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{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}{v}_{j}\text{\hspace{0.17em}}\text{isanoddvertexof}\text{\hspace{0.17em}}{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{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}{v}_{j}\text{\hspace{0.17em}}\text{isanevenvertexof}\text{\hspace{0.17em}}{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$.

Figure 6. ${J}_{2,8}$.

Figure 7. ${J}_{2,8}$.

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}\text{\hspace{0.17em}}{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

Figure 8. ${J}_{2,8}$.

Figure 9. ${J}_{2,8}$.

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 ${\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},\text{\hspace{0.17em}}\text{\hspace{0.17em}}{D}_{2}\stackrel{\text{clockwise}}{\Rightarrow}{D}_{3},\text{\hspace{0.17em}}\text{\hspace{0.17em}}{D}_{3}\stackrel{\text{clockwise}}{\Rightarrow}{D}_{1},$

${D}_{1}\stackrel{\text{counter-clockwise}}{\Rightarrow}{D}_{3},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{D}_{2}\stackrel{\text{counter-clockwise}}{\Rightarrow}{D}_{1},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{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. ■

Figure 10. ${\gamma}_{m}^{\infty}\left({J}_{3,4}\right)>4$.

Figure 11. ${\gamma}_{m}^{\infty}\left({J}_{3,4}\right)>4$.

Figure 12. ${\gamma}_{m}^{\infty}\left({J}_{3,4}\right)=5$.

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.

References

[1] Burger, A.P., Cockayne, E.J., et al. (2004) Infinite Order Domination in Graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 50, 179-194.

[2] Goddard, W., Hedetniemi, S.M. and Hedetniemi, S.T. (2005) Eternal Security in Graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 52, 169-180.

[3] Klostermeyer, W.F. and Mynhardt, C.M. (2016) Protecting a Graph with Mobile Guards. Applicable Analysis and Discrete Mathematics, 10, 1-29.

https://doi.org/10.2298/AADM151109021K

[4] Finbow, S., et al. (2015) Eternal Domination in 3 × n Grids. The Australasian Journal of Combinatorics, 61, 156-174.

[5] Messinger, M.E. and Delaney, A.Z. (2017) Closing the GAP: Eternal Domination on 3 × n Grids. Contributions to Discrete Mathematics, 12, 47-61.

[6] Mojdeh, D.A. and Ghameshlou, A.N. (2007) Domination in Jahangir Graph J2,m. International Journal of Contemporary Mathematical Sciences, 2, 1193-1199.

https://doi.org/10.12988/ijcms.2007.07122

[7] Goldwasser, J., Klostermeyer, W. and Mynhardt, C.M. (2013) Eternal Protection in Grid Graphs. Utilitas Mathematica, 91, 47-64.