ABSTRACT

In the eternal dominating set problem, guards form a dominating set on a graph and at each step, a vertex is attacked. 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 position after each attack If the new formed set of guards is still a dominating set of the graph then we successfully defended the attack. Our goal is to find the minimum number of guards required to eternally protect the graph. We call this number the m-eternal domination number and we denote it by ${\gamma }_m^{\infty }\left(G\right)$. In this paper we find the eternal domination number of Jahangir graph $J_{s,m}$ for $s=2,3$ and arbitrary m. We also find the domination number for $J_{3,m}$.

Keywords:

Jahangir Graph, Graph Protection, Domination Number, Eternal Domination

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.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

Cite this paper

Shaheen, R., Assaad, M. and Kassem, A. (2019) Domination and Eternal Domination of Jahangir Graph. Open Journal of Discrete Mathematics, 9, 68-81. https://doi.org/10.4236/ojdm.2019.93008

References