On the 2-Domination Number of Complete Grid Graphs

Ramy Shaheen, Suhail Mahfud, Khames Almanea

Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria.

DOI: 10.4236/ojdm.2017.71004                

Abstract

A set D of vertices of a graph G = (V, E) is called k-dominating if every vertex v ∈V-D is adjacent to some k vertices of D. The k-domination number of a graph G, γ_k (G), is the order of a smallest k-dominating set of G. In this paper we calculate the k-domination number (for k = 2) of the product of two paths P_m × P_n for m = 1, 2, 3, 4, 5 and arbitrary n. These results were shown an error in the paper [1].

Keywords

k-Dominating Set, k-Domination Number, 2-Dominating Set, 2-Domination Number, Cartesian Product Graphs, Paths

1. Introduction

Let $G=\left(V,E\right)$ be a graph. A subset of vertices $D\subseteq V$ is called a 2-dominating set of G if for every $v\in V$ , either $v\in D$ or v is adjacent to at least two vertices of D. The 2-domination number ${\gamma }_2\left(G\right)$ is equal to $\min \left\{\left|D\right|:D\text{isa}2-\text{dominatingsetof}G\right\}$ .

The Cartesian product G ´ H of two graphs G and H is the graph with vertex set $V\left(G\times H\right)=V\left(G\right)\times V\left(H\right)$ , where two vertices $\left(v_1,v_2\right)$ , $\left(u_1,u_2\right)\in G\times H$ are adjacent if and only if either $v_1{u}_1\in E\left(G\right)$ and $v_2=u_2$ or $v_2{u}_2\in E\left(H\right)$ and $v_1=u_1$ .

Let G be a path of order n with vertex set $V\left(G\right)=\left\{1,2,\cdots ,n\right\}$ . Then for two paths of order m and n respectively, we have $P_m\times P_n=\left\{\left(i,j\right):1\le i\le m,1\le j\le n\right\}$ . The jth column of $P_m\times P_n$ is $K_j=\left\{\left(i,j\right):i=1,\cdots ,m\right\}$ . If D is a 2-dominating set for $P_m\times P_n$ , then we put $W_j=D\cap K_j$ . Let $s_j=\left|W_j\right|$ . The sequence $\left(s_1,s_2,\cdots ,s_n\right)$ is called a 2-dominating sequence corresponding to D. For a graph G, we refer to minimum and maximum degrees by #Math_25# and $\Delta \left(G\right)$ , and for simplicity denoted those by δ and Δ, respectively. Also, we denote by $\left|V\right|$ and $\left|E\right|$ to order and size of graph G, respectively.

2. Notation and Terminology

Fink and Jacobson [2] [3] in 1985 to introduced the concept of multiple domination. A subset $D\subseteq V$ is k-dominating in G if every vertex of $V–D$ has at least k neighbors in D. The cardinality of a minimum k-dominating set is called the k-domination number ${\gamma }_k\left(G\right)$ of G. Clearly, $g_1\left(G\right)=g\left(G\right)$ . Naturally, every k-dominating set of a graph G contains all vertices of degree less than k. Of course, every $\left(k+1\right)$ -dominating set is also a k-dominating set and so ${\gamma }_k\left(G\right)\le {\gamma }_{k+1}\left(G\right)$ . Moreover, the vertex set V is the only $\left(\Delta +1\right)$ -dominating set but evidently it is not a minimum D-dominating set. Thus every graph G satisfies

${\gamma }_k\left(G\right)\le {\gamma }_{k+1}\left(G\right)\le \cdots \le {\gamma }_{\Delta }\left(G\right)<{\gamma }_{\Delta +1}\left(G\right)=\left|V\right|$ .

For a comprehensive treatment of domination in graphs, see the monographs by Haynes et al. [4] . Also, for more information see [5] [6] . Fink and Jacobson [2] , introduced the following theorems:

Theorem 2.1 [2] . If $k\ge 2$ , is an integer and G is a graph with $k\le \Delta \left(G\right)$ , then ${\gamma }_k\left(G\right)\ge \gamma \left(G\right)+k-2$ .

Theorem 2.2 [2] . If T is a tree, then ${\gamma }_2\left(T\right)\ge \frac{\left|T\right|+1}{2}$ .

In [6] , Hansberg and Volkmann, proved the following theorem.

Theorem 2.4 [6] . Let $G=\left(V,E\right)$ be a graph of order n and minimum degree δ and

let $k\in N$ . If $\frac{\delta +1}{\ln \left(\delta +1\right)}\ge 2k$ , then ${\gamma }_k\left(G\right)\le \frac{\left|V\right|}{\delta +1}\left(k\ln \left(\delta +1\right)+{\displaystyle \underset{i=0}{\overset{k-1}{\sum }}\frac{{\delta }^i}{i!{\left(\delta +1\right)}^{k-1}}}\right)$ .

Cockayne, et al. [7] , established an upper bound for the k-domination number of a graph G has minimum degree k, they gave the following result.

Theorem 2.3 [7] . Let G be a graph with minimum degree at least k, then

${\gamma }_k\left(G\right)\le \frac{k\left|V\right|}{\left(k+1\right)}$ .

Blidia, et al. [8] , studied the k-domination number. They introduced the following results.

Theorem 2.5 [8] . Let G be a bipartite graph and S is the set of all vertices of degree at

most $k–1$ , then ${\gamma }_k\left(G\right)\le \frac{\left|V\right|+\left|S\right|}{2}$ .

Favaron, et al. [9] , gave new upper bounds of ${\gamma }_k\left(G\right)$ .

Corollary 2.6 [9] . Let G be a graph of order n and minimum degree δ. If $k\le \delta$ is

an integer, then ${\gamma }_k\left(G\right)\le \frac{\delta }{2\delta +1-k}\left|V\right|.$

In [4] , Haynes et al. showed that the 2-domination number is bounded from below by the total domination number for every nontrivial tree.

Theorem 2.7 [4] . For every nontrivial tree, ${\gamma }_2\left(T\right)\ge {\gamma }_t\left(T\right)$ .

Also, Volkmann [10] gave the important following result.

Theorem 2.8 [10] . Let G be a graph with minimum degree $\delta \ge k+1$ , then

${\gamma }_{k+1}\left(G\right)\le \frac{\left|V\right|+{\gamma }_k\left(G\right)}{2}.$

Shaheen [11] considered the 2-domination number of Toroidal grid graphs and gave an upper and lower bounds. Also, in [12] , he introduced the following results.

Theorem 2.9 [12] .

1) ${\gamma }_2\left(C_n\right)=\lceil n/2\rceil$ .

2) ${\gamma }_2\left(C_3\times C_n\right)=n:n\equiv 0\left(\mathrm{mod}3\right)$ ,

${\gamma }_2\left(C_3\times C_n\right)=n+1:n\equiv 1,2\left(\mathrm{mod}3\right)$ .

3) ${\gamma }_2\left(C_4\times C_n\right)=n+\lceil n/2\rceil :n\equiv 0,3,5\left(\mathrm{mod}8\right)$ ,

${\gamma }_2\left(C_4\times C_n\right)=n+\lceil n/2\rceil +1:n\equiv 1,2,4,6,7\left(\mathrm{mod}14\right)$ .

4) ${\gamma }_2\left(C_5\times C_n\right)=2n$ .

5) ${\gamma }_2\left(C_6\times C_n\right)=2n:n\equiv 0\left(\mathrm{mod}3\right)$ ,

${\gamma }_2\left(C_6\times C_n\right)=2n+2:n\equiv 1,2\left(\mathrm{mod}3\right)$ .

6) ${\gamma }_2\left(C_7\times C_n\right)=\lceil 5n/2\rceil :n\equiv 0,3,11\left(\mathrm{mod}14\right)$ ,

${\gamma }_2\left(C_7\times C_n\right)=\lceil 5n/2\rceil +1:n\equiv 5,6,7,8,9,10\left(\mathrm{mod}14\right)$ ,

${\gamma }_2\left(C_7\times C_n\right)=\lceil 5n/2\rceil +2:n\equiv 1,2,4,12,13\left(\mathrm{mod}14\right)$ .

In this paper we calculate the k-domination number (for k = 2) of the product of two paths $P_m\times P_n$ for m = 1, 2, 3, 4, 5 and arbitrary n. These results were shown an error in the paper [1] . We believe that these results were wrong. In our paper we will provide improved and corrected her, especially for m = 3, 4, 5.

The following formulas appeared in [1] ,

${\gamma }_2\left(P_n\right)=\lceil \left(n+1\right)/2\rceil \cdot {\gamma }_2\left(P_2\times P_n\right)=n\cdot {\gamma }_2\left(P_3\times P_n\right)=2n-\lceil n/2\rceil \cdot {\gamma }_2\left(P_4\times P_n\right)=2n.$

${\gamma }_2\left(P_5\times P_n\right)=3n-\lceil n/2\rceil \cdot {\gamma }_2\left(P_{2k+1}\times P_n\right)=\left(k+1\right)n-\lceil n/2\rceil .$

$\begin{array}{l}{\gamma }_2\left(P_m\times P_n\right)=\lceil m/2\rceil n-\lceil n/2\rceil :m\equiv 1\left(\mathrm{mod}2\right),\\ {\gamma }_2\left(P_m\times P_n\right)=\lceil m/2\rceil n:m\equiv 0\left(\mathrm{mod}2\right).\end{array}$

In this paper, we correct the results in [1] and proves the following:

${\gamma }_2\left(P_n\right)=\lceil \left(n+1\right)/2\rceil \cdot {\gamma }_2\left(P_2\times P_n\right)=n\cdot {\gamma }_2\left(P_3\times P_n\right)=n+\lceil n/3\rceil .$

$\begin{array}{l}{\gamma }_2\left(P_4\times P_n\right)=2n-\lfloor n/4\rfloor :n\equiv 3,7\left(\mathrm{mod}8\right),\\ {\gamma }_2\left(P_4\times P_n\right)=2n-\lfloor n/4\rfloor +1:n\equiv 0,1,2,4,5,6\left(\mathrm{mod}8\right).\end{array}$

$\begin{array}{l}{\gamma }_2\left(P_5\times P_n\right)=2n+\lceil n/7\rceil :n\equiv 1,2,3,5\left(\mathrm{mod}7\right),\\ {\gamma }_2\left(P_5\times P_n\right)=2n+\lceil n/7\rceil +1:n\equiv 0,4,6\left(\mathrm{mod}7\right).\end{array}$

3. Main Results

Our main results here are to establish the domination number of Cartesian product of two paths $P_m$ and $P_n$ for m = 1, 2, 3, 4, 5 and arbitrary n. We study 2-dominating sets in complete grid graphs using one technique: by given a minimum of upper 2-dominating set D of $P_m\times P_n$ and then we establish that D is a minimum 2-domi- nating set of $P_m\times P_n$ for several values of m and arbitrary n. Definitely we have ${\gamma }_2\left(P_m\times P_n\right)=\left|D\right|$ .

Let G be a path of order n with vertex set $V\left(G\right)=\left\{1,2,\cdots ,n\right\}$ . For two paths of order m and n respectively is:

$P_m\times P_n=\left\{\left(i,j\right):1\le i\le m,1\le j\le n\right\}$ . The jth column $P_m\times P_n$ is $K_j=\left\{\left(i,j\right):i=1,\cdots ,m\right\}$ .

If D is a 2-dominating set for $P_m\times P_n$ then we put $W_j=D\cap K_j$ . Let $s_j=\left|W_j\right|$ . The sequence $\left(s_1,s_2,\cdots ,s_n\right)$ is called a 2-dominating sequence corresponding to D. Always we have $s_1,s_n\ge \lceil m/3\rceil$ . Suppose that $s_j=0$ for some j (where j ¹ 1 or n). The vertices of the jth column can only be 2-dominated by vertices of the (j − 1)st columns and (j + 1)st columns. Thus we have $s_{j-1}+s_{j+1}=2m$ , then $s_{j-1}=s_{j+1}=m$ . In general $s_{j-1}+4s_j+s_{j+1}\ge 2m$ .

Notice 3.1.

1) The study of 2-dominating sequence $\left(s_1,s_2,\cdots ,s_n\right)$ is the same as the study of the 2-dominating sequence $\left(s_n,s_{n-1},\cdots ,s_1\right)$ .

2) If subsequence $\left(s_j,s_{j+1},\cdots ,s_{j+k}\right)$ is not possible, then its reverse $\left(s_{j+k},\cdots ,s_{j+1},s_j\right)$ is not possible.

3) We say that two subsequences $\left(s_j,\cdots ,s_{j+q}\right),\left(s_{j+q+1},\cdots ,s_{j+r}\right)$ are equivalent, if the sequence $\left(s_j,\cdots ,s_{j+q},s_{j+q+1},\cdots ,s_{j+r}\right)$ is possible.

We need the useful following lemma.

Lemma 3.1. There is a minimum 2-dominating set for $P_m\times P_n$ with 2-dominating sequence $\left(s_1,s_2-,\cdots ,s_n\right)$ such that, for all $j=1,2,\cdots ,n$ , is $\lfloor m/4\rfloor \le s_j\le \lceil 3m/4\rceil$ .

Proof. Let D be a minimum 2-dominating set for $P_m\times P_n$ with 2-dominating sequence $\left(s_1,s_2-,\cdots ,s_n\right)$ . Assume that for some j, s_j is large. Then we modify D by moving two vertices from column j, one to column j − 1 and another one to column j + 1, such that the resulting set is still 2-dominating set for $P_m\times P_n$ . For $1\le i\le m$ and $1\le j\le n$ , let $W=D\cap \left\{\left(i,j\right),\left(i+1,j\right),\left(i+2,j\right),\left(i+3,j\right)\right\}$ . If $\left|W\right|=4$ , then we define $D_1=\left(D–W\right)\cup \left\{\left(i,j\right),\left(i+1,j-1\right),\left(i+2,j+1\right),\left(i+3,j\right)\right\}$ , see Figure 1. We repeat this process if necessary eventually leads to a 2-dominating set with required properties. Also, we get D₁ is a 2-dominating set for $P_m\times P_n$ with $\left|D\right|=\left|D_1\right|$ . Thus, we can assume that every four consecutive vertices of the jth column include at most three vertices of D. This implies that $s_j\le \lceil 3m/4\rceil$ , for all 1 ≤ j ≤ n.

To prove the lower bound, we suppose that $\left|K_j\cap D\right|$ is be a maximum, i.e., $s_j=\lceil 3m/4\rceil$ . Then for each $\left(i,j\right)\notin D$ , we have

$\left|\left\{\left(i-1,j+1\right),\left(i,j+1\right),\left(i+1,j+1\right)\right\}\cap D\right|\ge 1$ . When $s_j=\lceil 3m/4\rceil$ , there at must $m-\lceil 3m/4\rceil =\lfloor m/4\rfloor$ vertices does not in $K_j\cap D$ . This implies that $s_{j+1}\ge \lfloor m/4\rfloor$ . So, the same as for $s_{j-1}\ge \lfloor m/4\rfloor$ . □

By Lemma 3.1, always we have a minimum 2-dominating set D with 2-dominating sequence $\left(s_1,s_2,\cdots ,s_n\right)$ , such that $\lfloor m/4\rfloor \le s_j\le \lceil 3m/4\rceil$ , for all $j=1,2,\cdots ,n$ .

Lemma 3.2. ${\gamma }_2\left(P_n\right)=\lceil \frac{n+1}{2}\rceil$ .

Figure 1. Modify D.

Proof. Let $D=\left\{\left(2k-1\right);1\le k\le \lceil \frac{n}{2}\rceil \right\}$ .

We have D is a 2-dominating set of P_n for $n\equiv 1\left(\mathrm{mod}2\right)$ with $\left|D\right|=\lceil \frac{n+1}{2}\rceil$ , also $D\cup \left\{\left(n\right)\right\}$ is a 2-dominating set of P_n for $n\equiv 0\left(\mathrm{mod}2\right)$ with $\left|D\cup \left\{\left(n\right)\right\}\right|=\lceil \frac{n+1}{2}\rceil$ .

Let D₁ be a minimum 2-dominating set for P_n with $V\left(P_n\right)=\left\{x_1,x_2,\cdots ,x_n\right\}$ . Since $x_1{x}_n\notin E\left(P_n\right)$ , we need to $x_1,x_n\in D_1$ , also if $x_j\notin D_1$ then $x_{j-1},x_{j+1}$ are belong to D₁,

this implies that $x_{2j-1}\in D_1$ for $2\le j\le \lfloor \frac{n}{2}\rfloor$ . Thus implies that

$\left|D_1\right|\ge 2+\lfloor \frac{n}{2}\rfloor -1=\lceil \frac{n+1}{2}\rceil$ . We result that ${\gamma }_2\left(P_n\right)=\lceil \frac{n+1}{2}\rceil$ . □

Theorem 3.1. ${\gamma }_2\left(P_2\times P_n\right)=n$ .

Proof. Let a set $D=\left\{\left(1,2k-1\right):1\le k\le \lceil \frac{n}{2}\rceil \right\}\cup \left\{\left(2,2k\right):1\le k\le \lfloor \frac{n}{2}\rfloor \right\}$ .

It is clear that $\left|D\right|=n$ . (1)

We can check that D is 2-dominating set for $P_2\times P_n$ , see Figure 2. Let D₁ be a minimum 2-dominating set for $P_2\times P_n$ with dominating sequence $\left(s_1,\cdots ,s_n\right)$ . If $s_i\ge 1$ for all

$j=1,\cdots ,n$ , then $\left|D_1\right|={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}\ge n$ . (2)

Let $s_j=0$ for some j, then $s_{j-1}=s_{j+1}=2$ , also we have $s_1\ge 1$ and $s_n\ge 1$ . Now we define a new sequence $\left({s^{\prime }}_1,\cdots ,{s^{\prime }}_n\right)$ , (not necessarily a 2-dominating sequence) as follows:

For $s_j=2$ , if $j=1$ or n, we put ${s^{\prime }}_j=s_j–1$ , ${s^{\prime }}_2=s_2+1/2$ and ${s^{\prime }}_{n-1}=s_{n-1}+1/2$ .

If $j\ne 1$ or n, we put ${s^{\prime }}_j=s_j–1$ , ${s^{\prime }}_{j-1}=s_{j-1}+1/2$ and ${s^{\prime }}_{j+1}=s_{j+1}+1/2$ .

Otherwise ${s^{\prime }}_j=s_j$ .

We get a sequence $\left({s^{\prime }}_1,\cdots ,{s^{\prime }}_n\right)$ have property that each ${s^{\prime }}_j\ge 1$ with

$\left|D\right|={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s^{\prime }}_j}\ge n$ . (3)

By (1), (2) and (3) is ${\gamma }_2\left(P_2\times P_n\right)=n$ . This completes the proof of the theorem. □

Theorem 3.2. ${\gamma }_2\left(P_3\times P_n\right)=n+\lceil \frac{n}{3}\rceil$ .

Proof. Let $\begin{array}{l}D=\left\{\left(2,3k-2\right):1\le k\le \lceil \frac{n}{3}\rceil \right\}\cup \left\{\left(2,3k\right):1\le k\le \lfloor \frac{n}{3}\rfloor \right\}\\ \cup \left\{\left(1,3k-1\right),\left(3,3k-1\right):1\le k\le \lceil \frac{n-1}{3}\rceil \right\}\end{array}$ .

Figure 2. A 2-dominating set for P₂ × P₁₀.

$\begin{array}{l}{D}^{\prime }=\left\{\left(1,3k-2\right),\left(3,3k-2\right):1\le k\le \lceil \frac{n}{3}\rceil \right\}\cup \left\{\left(2,3k-1\right):1\le k\le \lceil \frac{n-1}{3}\rceil \right\}\\ \cup \left\{\left(2,3k\right):1\le k\le \lfloor \frac{n}{3}\rfloor \right\}\end{array}$ .

We have $\left|D\right|=n+\lceil \frac{n}{3}\rceil$ and $\left|D^{\prime }\right|=n+\lceil \frac{n}{3}\rceil$ . (4)

By definition D and $D^{\prime }$ we note that

D is 2-dominating set for $P_3\times P_n$ when $n=0,2\left(\mathrm{mod}3\right)$ , (see Figure 3, for P₃ × P₁₄).

$D^{\prime }$ is 2-dominating set for $P_3\times P_n$ when $n=1\left(\mathrm{mod}3\right)$ , (see Figure 4, for P₃ × P₁₀).

Let D₁ be a minimum 2-dominating set for $P_3\times P_n$ with 2-dominating sequence $\left(s_1,\cdots ,s_n\right)$ we have $s_1,s_n\ge 1$ and

if $s_1,s_n=1$ then $s_2,s_{n-1}\ge 2$ ,

if $s_1,s_n=2$ then $s_2,s_{n-1}\ge 1$ .

Also for $1<j<n$ , if $s_j=0$ then $s_{j-1}=s_{j+1}=3,$

$s_j=1$ then $s_{j-1}+s_{j+1}\ge 3,$

$s_j=2$ then $s_{j-1}+s_{j+1}\ge 2,$

If no one of $s_j=0$ for all j, then $\left|D_1\right|={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}\ge n+\lceil \frac{n}{3}\rceil$ . (5)

Let $s_j=0$ ( $j\ne 1$ or n) for some j, we define a sequence $\left({s^{\prime }}_1,\cdots ,{s^{\prime }}_n\right)$ , (not necessarily a 2-dominating sequence ) as follows:

If $s_j=3$ , then we put ${s^{\prime }}_j=s_j–1$ , ${s^{\prime }}_{j-1}=s_{j-1}+1/2$ and ${s^{\prime }}_{j+1}=s_{j+1}+1/2$ , otherwise

${s^{\prime }}_j=s_j$ . We have $\left|D_1\right|={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j^{\backslash }}$ . We note that the sequence $\left({s^{\prime }}_1,\cdots ,{s^{\prime }}_n\right)$ have the

property if ${s^{\prime }}_j=1$ then ${s^{\prime }}_{j-1}+{s^{\prime }}_{j+1}\ge 3$ . Thus implies that

$\left|D_1\right|={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s^{\prime }}_j}\ge n+\lceil \frac{n}{3}\rceil$ . (6)

From (4), (5) and (6) we get the required result. □

Theorem 3.3. ${\gamma }_2\left(P_4\times P_n\right)=\{\begin{array}{l}2n-\lfloor \frac{n}{4}\rfloor :n\equiv 3,7\left(\mathrm{mod}8\right),\\ 2n-\lfloor \frac{n}{4}\rfloor +1:n\equiv 0,1,2,4,5,6\left(\mathrm{mod}8\right).\end{array}$

Figure 3. A 2-dominating set for P₃ × P₁₄.

Figure 4. A 2-dominating set for P₃ × P₁₀.

Proof. Let a set D defined as follows:

$\begin{array}{l}D=\{\left\{\left(2,1\right),\left(3,1\right)\right\}\cup \left\{\left(1,4k-2\right),\left(4,4k-2\right);1\le k\le \lceil \frac{n-1}{4}\rceil \right\}\\ \cup \left\{\left(2,8k-5\right);1\le k\le \lceil \frac{n-2}{8}\rceil \right\}\\ \cup \left\{\left(1,8k-4\right),\left(3,8k-4\right),\left(4,8k-4\right);1\le k\le \lceil \frac{n-3}{8}\rceil \right\}\\ \cup \left\{\left(2,8k-3\right);1\le k\le \lceil \frac{n-4}{8}\rceil \right\}\cup \left\{\left(3,8k-1\right);1\le k\le \lceil \frac{n-6}{8}\rceil \right\}\\ \cup \left\{\left(1,8k\right),\left(2,8k\right),\left(4,8k\right);1\le k\le \lceil \frac{n-7}{8}\rceil \right\}\cup \left\{\left(3,8k+1\right);1\le k\le \lfloor \frac{n-1}{8}\rfloor \right\}\}\end{array}$

$D^{\prime }=\left\{\left(2,n\right)\right\},D^{″}=\left\{\left(3,n\right)\right\}$ .

We can check that the following sets are 2-dominating set for $P_4\times P_n$ (see Figure 5, for $P_4\times P_{11}$ ) as indicated:

D is 2-dominating set for $P_4\times P_n$ when $n\equiv 0,4\left(\mathrm{mod}8\right)$ .

$D\cup D^{\prime }$ is 2-dominating set for $P_4\times P_n$ when $n\equiv 1,2,7\left(\mathrm{mod}8\right)$ .

$D\cup D^{″}$ is 2-dominating set for $P_4\times P_n$ when $n\equiv 3,5,6\left(\mathrm{mod}8\right)$ .

We have

$\left|D\right|=\left\{\begin{array}{l}2n-\lfloor \frac{n}{4}\rfloor -1:n\equiv 3,7\left(\mathrm{mod}8\right),\\ 2n-\lfloor \frac{n}{4}\rfloor :n\equiv 1,2,5,6\left(\mathrm{mod}8\right),\\ 2n-\lfloor \frac{n}{4}\rfloor +1:n\equiv 0,4\left(\mathrm{mod}8\right).\end{array}\right\}$

Let D₁ be a minimum 2-dominating set for $P_4\times P_n$ with 2-dominating sequence $\left(s_1,\cdots ,s_n\right)$ we shall show that

$\left|D_1\right|=\left\{\begin{array}{l}2n-\lfloor \frac{n}{4}\rfloor :n\equiv 3,7\left(\mathrm{mod}8\right),\\ 2n-\lfloor \frac{n}{4}\rfloor +1:n\equiv 0,1,2,4,5,6\left(\mathrm{mod}8\right).\end{array}\right\}$

By Lemma 3.1, we have $1\le s_j\le 3$ . Thus

If $s_j=1$ then $s_{j-1}+s_{j+1}\ge 5$ .

If $s_j=2$ then $s_{j-1}+s_{j+1}\ge 2$ .

If $s_j=3$ then $s_{j-1}+s_{j+1}\ge 2$ .

Also, we have $s_1,s_n\ge 2$ . If $s_1,s_n=2$ then $s_2,s_{n-1}\ge 2$ , and if $s_1,s_n=3$ then

Figure 5. A 2-dominating set for P₄ × P₁₁.

$s_2,s_{n-1}\ge 1$ .

We define a new set ${D^{\prime }}_1$ with sequence $\left({s^{\prime }}_1,\cdots ,{s^{\prime }}_n\right)$ , (not necessarily a 2-dominating

sequence) as follows: if $s_j\ge 2$ , let $M_j=s_j-\frac{7}{4}$ . Now, for $j=2$ to $j=n-1$ , if

$s_j\ge 2$ , then we put

${s^{\prime }}_j=s_j-M_j$ , ${s^{\prime }}_{j-1}=s_{j-1}+\frac{M_j}{2}$ and ${s^{\prime }}_{j+1}=s_{j+1}+\frac{M_j}{2}$

Thus, for $3\le j\le n-2$ , we have $s_j\ge \frac{7}{4}$ . Since if $s_j\ge 2$ then ${s^{\prime }}_j\ge \frac{7}{4}$ and if $s_j=1$ , then $s_{j-1}+s_{j+1}=5$ this implies that $M_{j-1}+M_{j+1}=5-\frac{14}{4}=\frac{6}{4}$ , which implies that ${s^{\prime }}_j=s_j+\frac{M_{j-1}}{2}+\frac{M_{j+1}}{2}=1+\frac{3}{4}=\frac{7}{4}.$

We have three cases:

Case 1: $s_1,s_n\ge 2$ , then $s_2,s_{n-1}\ge 2$ , these implies that ${s^{\prime }}_1\ge s_1+\frac{1}{8}$ and ${s^{\prime }}_n\ge s_n+\frac{1}{8}$ also

$\left|D_1\right|={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s^{\prime }}_j=}{s^{\prime }}_1+{s^{\prime }}_n+{\displaystyle \underset{j=2}{\overset{n-1}{\sum }}{s^{\prime }}_j\ge 2+\frac{1}{8}+2}+\frac{1}{8}+\frac{7\left(n-2\right)}{4}=\frac{7n}{4}+\frac{3}{4}$ .

Case 2: $s_1,s_n=3$ then $s_2,s_{n-1}\ge 2$ . Thus implies that ${s^{\prime }}_1,{s^{\prime }}_n=3$ and

${s^{\prime }}_2,{s^{\prime }}_{n-1}\ge 1+\frac{1}{8}.$ Then

$\left|D_1\right|={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s^{\prime }}_j=}{s^{\prime }}_1+{s^{\prime }}_2+{s^{\prime }}_{n-1}+{s^{\prime }}_n+{\displaystyle \underset{j=2}{\overset{n-2}{\sum }}{s^{\prime }}_j\ge 3+1+\frac{1}{8}+3+1+\frac{1}{8}+\frac{7}{4}}=\frac{7n}{4}+\frac{5}{4}$

Case 3: $s_1=2,s_n=3$ and $s_2\ge 2,s_{n-1}\ge 1\text{or}{s}_1=3,s_n=2$ and $s_2\ge 1,s_{n-1}\ge 2$ . Two cases are similar by symmetry. We consider the first case:

$s_1=2,s_2\ge 2$ and $s_n=3,s_{n-1}\ge 1$ , this implies that

${s^{\prime }}_1=2+\frac{1}{8},{s^{\prime }}_2=\frac{7}{4},{s^{\prime }}_n=3,{s^{\prime }}_{n-1}=1+\frac{1}{8}$ and

$\left|D_1\right|={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s^{\prime }}_j=}{s^{\prime }}_1+{s^{\prime }}_2+{s^{\prime }}_{n-1}+{s^{\prime }}_n+{\displaystyle \underset{j=3}{\overset{n-2}{\sum }}{s^{\prime }}_j\ge 2+\frac{1}{8}+\frac{7}{4}}+ 3+1+\frac{1}{8}+\frac{7}{4}\left(n-4\right)=\frac{7n}{4}+1$

But, we have the 2-domination number is positive integer number, also we have

$2n-\lfloor \frac{n}{4}\rfloor =\frac{7n}{4}+\frac{3}{4}$ for $n\equiv 3,7\left(\mathrm{mod}8\right)$ ,

$2n-\lfloor \frac{n}{4}\rfloor +1=\{\begin{array}{l}\frac{7n}{4}+1\text{For}n\equiv 0,4\left(\mathrm{mod}8\right),\\ \frac{7n}{4}+\frac{5}{4}\text{For}n\equiv 1,5\left(\mathrm{mod}8\right),\\ \frac{7n}{4}+\frac{6}{4}\text{For}n\equiv 2,6\left(\mathrm{mod}8\right),\end{array}$

Thus implies that

$\left|D_1\right|\ge \left\{\begin{array}{l}2n-\lfloor \frac{n}{4}\rfloor ;n\equiv 3,7\left(\mathrm{mod}8\right),\\ 2n-\lfloor \frac{n}{4}\rfloor +1;n\equiv 0,1,2,4,5,6\left(\mathrm{mod}8\right),\end{array}\right\}$

Finally, we get

$\begin{array}{l}{\gamma }_2\left(P_4\times P_n\right)=2n-\lfloor \frac{n}{4}\rfloor :n\equiv 3,7\left(\mathrm{mod}8\right),\\ {\gamma }_2\left(P_4\times P_n\right)=2n-\lfloor \frac{n}{4}\rfloor +1:n\equiv 0,1,2,4,5,6\left(\mathrm{mod}8\right),\end{array}$

This complete the proof of the theorem. □

Theorem 3.4.

${\gamma }_2\left(P_5\times P_n\right)=\{\begin{array}{l}2n+\lceil \frac{n}{7}\rceil :n\equiv 1,2,3,5\left(\mathrm{mod}7\right),\\ 2n+\lceil \frac{n}{7}\rceil +1:n\equiv 0,4,6\left(\mathrm{mod}7\right).\end{array}$

Proof. Let a set D defined as follows:

$\begin{array}{l}D=\{\left\{\left(2,1\right),\left(4,1\right)\right\}\cup \left\{\left(1,j\right),\left(2,j\right),\left(5,j\right):j\equiv 2\left(\mathrm{mod}7\right)\right\}\\ \cup \left\{\left(3,j\right):j\equiv 3\left(\mathrm{mod}7\right)\right\}\cup \left\{\left(1,j\right),\left(4,j\right),\left(5,j\right):j\equiv 4\left(\mathrm{mod}7\right)\right\}\\ \cup \left\{\left(2,j\right),\left(3,j\right):j\equiv 5\left(\mathrm{mod}7\right)\right\}\cup \left\{\left(2,j\right),\left(5,j\right):j\equiv 6\left(\mathrm{mod}7\right)\right\}\\ \cup \left\{\left(1,j\right),\left(4,j\right):j\equiv 0\left(\mathrm{mod}7\right)\right\}\cup \left\{\left(3,j\right),\left(4,j\right):j\equiv 1\left(\mathrm{mod}7\right)\right\}\text{and}j\ne 1\}\end{array}$

We can check that the following sets are 2-dominating set for $P_5\times P_n$ (see Figure 6, for $P_5\times P_{23}$ ) as indicated:

$\begin{array}{l}\left\{D-\left\{K_n\cap D\right\}\right\}\cup \left\{\left(2,n\right),\left(3,n\right),\left(5,n\right)\right\}:n\equiv 1\left(\mathrm{mod}7\right).\\ D\cup \left\{\left(2,n\right)\right\}:n\equiv 0,4\left(\mathrm{mod}7\right).\\ D:n\equiv 2\left(\mathrm{mod}7\right).\\ \left\{D-\left\{K_n\cap D\right\}\right\}\cup \left\{\left(2,n\right),\left(4,n\right)\right\}:n\equiv 3,5\left(\mathrm{mod}7\right).\\ \left\{D-\left\{K_n\cap D\right\}\right\}\cup \left\{\left(1,n\right),\left(3,n\right),\left(5,n\right)\right\}:n\equiv 6\left(\mathrm{mod}7\right).\end{array}$

We have $D\le 2n+\lceil \frac{n}{7}\rceil$ and

${\gamma }_2\left(P_5\times P_n\right)\le \{\begin{array}{l}2n+\lceil \frac{n}{7}\rceil :n\equiv 1,2,3,5\left(\mathrm{mod}7\right),\\ 2n+\lceil \frac{n}{7}\rceil +1:n\equiv 0,4,6\left(\mathrm{mod}7\right).\end{array}$

This complete the proof of the theorem. □

Lemma 3.3. The following cases are not possible:

1) (1, 2, 3, 1).

2) (1, 2, 1).

3) (1, 4, 1, 1).

Figure 6. A 2-dominating set for P₅ × P₂₃.

4) (1, 3, 1, 3, 1, 3).

5) (2, 1, 3).

6) (2, 2, 2, 2, 2, 2).

Proof. It follows directly from the drawing.

Lemma 3.4.

1) There is one case for subsequence $\left(s_j,s_{j+1},s_{j+2},s_{j+3},s_{j+4}\right)=\left(2,2,2,2,2\right)$ .

2) There is one case for subsequence $\left(s_j,s_{j+1},s_{j+2},s_{j+3}\right)=\left(1,3,1,3\right)$ .

3) There is one case for subsequence $\left(s_j,s_{j+1},s_{j+2},s_{j+3},s_{j+4}\right)=\left(1,3,1,3,1\right)$ .

4) There is one case for subsequence $\left(s_j,s_{j+1},s_{j+2},s_{j+3},s_{j+4}\right)=\left(1,2,3,2,1\right)$ .

Proof. It follows directly from the drawing (see Figure 7).

Lemma 3.5.

1) ${\displaystyle \underset{j}{\overset{j+3}{\sum }}{s}_j}\ge 8$ .

2) ${\displaystyle \underset{j}{\overset{j+5}{\sum }}{s}_j}\ge 12$ .

3) ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}\ge 14$ .

4) If $s_j=3$ then ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}\ge 15$ .

5) If $s_j=4$ then ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}\ge 16$ .

Proof. 1) By Lemma 3.3, imply that ${\displaystyle \underset{j}{\overset{j+3}{\sum }}{s}_j}\ge 8$ .

2) By 1, we have ${\displaystyle \underset{j}{\overset{j+3}{\sum }}{s}_j}\ge 8$ . If ${\displaystyle \underset{j}{\overset{j+3}{\sum }}{s}_j}=8$ , then we have the cases

$\left(s_j,s_{j+1},s_{j+2},s_{j+3}\right)=\left(1,2,3,2\right),\left(1,3,1,3\right),\left(1,3,2,2\right),\left(1,4,1,2\right),\left(2,2,2,2\right)$ .

From Lemma 3.3, we have $s_{j+4}+s_{j+5}\ge 4$ , this implies that ${\displaystyle \underset{j}{\overset{j+5}{\sum }}{s}_j}\ge 12$ .

If ${\displaystyle \underset{j}{\overset{j+4}{\sum }}{s}_j}\ge 9$ then $s_{j+4}+s_{j+5}\ge 3$ . This implies that ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}\ge 12$ .

3) We have ${\displaystyle \underset{j}{\overset{j+2}{\sum }}{s}_j}\ge 5$ and ${\displaystyle \underset{j+4}{\overset{j+6}{\sum }}{s}_j}\ge 5$ . If ${\displaystyle \underset{j+4}{\overset{j+6}{\sum }}{s}_j}=5$ , then there is one case

$\left(s_{j+4},s_{j+5},s_{j+6}\right)=\left(1,3,1\right)$ (where the cases $\left(1,2,1\right),\left(1,2,2\right)$ are not possible). But the

case $\left(1,3,1\right)$ is not compatible with any of the cases when ${\displaystyle \underset{j}{\overset{j+3}{\sum }}{s}_j}=8$ , this implies that

Figure 7. Cases 1, 2, 3 and 4 of Lemma 3.4.

${\displaystyle \underset{j}{\overset{j+3}{\sum }}{s}_j}\ge 9$ . Then ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}\ge 14$ (where the case $\left(1,3,1,3,1,3\right)$ is not possible). If ${\displaystyle \underset{j+4}{\overset{j+6}{\sum }}{s}_j}\ge 6$ then ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}={\displaystyle \underset{j}{\overset{j+3}{\sum }}{s}_j}+{\displaystyle \underset{j+4}{\overset{j+6}{\sum }}{s}_j}\ge 8+6=14$ .

4) We have $s_j\ge 3$ , then from 2 is ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}\ge 15$ .

5) We have $s_j\ge 4$ , then from 2 is ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}\ge 16$ . This complete the proof of the Lemma. □

Lemma 3.6. If ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}=14$ , then $s_j=1$ or $s_{j+6}=1$ .

Proof. We suppose the contrary $s_j,s_{j+6}\ge 2$ . From Lemma 3.5, $s_j,s_{j+6}<3$ , else

${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}\ge 15$ . Now, we must study the case $s_j=s_{j+6}=2$ . We have ${\displaystyle \underset{j+2}{\overset{j+5}{\sum }}{s}_j}=10$ , by Lem-

ma 3.3, the case $\left(2,2,2,2,2,2\right)$ is not possible, this implies that not all elements of the subsequence $\left(s_{j+1},\cdots ,s_{j+5}\right)$ are equal to the value 2. If $s_{j+1},s_{j+2},s_{j+3},s_{j+4},s_{j+5}\ge 2$

where at least one of them is equal or greater than 3, then ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}\ge 15$ , this is a contradiction with ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}=14$ . Now, we have ${\displaystyle \underset{j}{\overset{j+5}{\sum }}{s}_j}=10$ , where one of the subsequence ele-

ment $\left(s_{j+1},\cdots ,s_{j+5}\right)$ is at most equal the value 1 (where $1\le s_j\le 4$ ). We consider the cases $s_j=1$ for $j+1\le j\le j+5$ :

1) $s_{j+1}=1$ or $s_{j+5}=1$ (where two cases are similar), we study the case $s_{j+1}=1$

then $s_{j+2}=4$ , these implies that $s_j+s_{j+1}+s_{j+2}=7$ . By Lemma 3.5, we have ${\displaystyle \underset{j+3}{\overset{j+6}{\sum }}{s}_j}\ge 8$ then ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}\ge 15$ , this is a contradiction.

2) $s_{j+2}=1$ or $s_{j+4}=1$ (where two cases are similar), we study the case $s_{j+2}=1$ then $s_{j+1}\ge 3$ , (because the case $\left(2,2,1\right)$ is not possible). If $s_{j+1}=3$ then $s_{j+3}\ge 3$

and we have $s_{j+6}=2$ then ${\displaystyle \underset{j+4}{\overset{j+5}{\sum }}{s}_j}\ge 4$ (because two cases $\left(1,2,2\right),\left(2,1,2\right)$ are not possible). Thus implies that ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}\ge 2+3+1+3+4+2=15$ , this is a contradiction.

3) $s_{j+3}=1$ , then we have two subcases results from $s_{j+2}+s_{j+4}\ge 6$ :

Subcase 1: $s_{j+2}=s_{j+4}=3$ then $s_{j+1},s_{j+5}\ge 2$ (because two cases

$\left(s_j,s_{j+1},s_{j+2}\right)=\left(2,1,3\right)$ and $\left(s_{j+4},s_{j+5},s_{j+6}\right)=\left(3,1,2\right)$ are not possible). Thus implies

that ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}\ge 15$ , this is a contradiction.

Subcase 2: If $s_{j+2}=2,s_{j+4}=4$ or conversely (two cases are similar in studying), so

we will study case $s_{j+2}=2,s_{j+4}=4$ then $s_{j+5}\ge 1,$ if $s_{j+5}\ge 2$ , then ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}\ge 15$ , because $s_{j+4}+s_{j+5}+s_{j+6}\ge 8$ , we have ${\displaystyle \underset{j}{\overset{j+3}{\sum }}{s}_j}\ge 8$ . Then ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}\ge 15$ , this is a contradiction).

If $s_{j+5}=1$ , then $s_{j+4}+s_{j+5}+s_{j+6}=7$ . We have ${\displaystyle \underset{j}{\overset{j+3}{\sum }}{s}_j}\ge 8$ . This implies that ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}\ge 15$ this is a contradiction.

Finally, we get if ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}=14$ , then $s_j=1$ or $s_{j+6}=1$ . This completely the proof. □

Result 3.1. If ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}=14$ , then from Lemma 3.6, we have the cases for subsequence

$\left(s_j,s_{j+1},s_{j+2},s_{j+3},s_{j+4},s_{j+5},s_{j+6}\right)$ :

$\begin{array}{l}{a}_1:\left(1,2,3,2,1,4,1\right),a_2:\left(1,2,3,2,2,2,2\right),a_3:\left(1,2,3,2,2,3,1\right),\\ a_4:\left(1,2,3,3,1,3,1\right),a_5:\left(1,3,1,3,1,4,1\right),a_6:\left(1,3,1,3,2,2,2\right),\\ a_7:\left(1,3,1,3,2,3,1\right),a_8:\left(1,3,1,3,3,2,1\right),a_9:\left(1,3,1,4,1,3,1\right),\\ a_{10}:\left(1,3,2,2,2,2,2\right),a_{11}:\left(1,3,2,2,2,3,1\right),a_{12}:\left(1,3,2,2,3,2,1\right),\\ a_{13}:\left(1,3,2,3,1,3,1\right),a_{14}:\left(1,4,1,2,3,2,1\right),a_{15}:\left(1,4,1,3,1,3,1\right).\end{array}$

It is 15 cases (where $s_j=1$ with ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}=14$ ). We have three cases with $s_{j+1}=2$ ,

$s_{j+1}=3$ and $s_{j+1}=4$ .

Case 1: $s_{j+1}=2$ (including the cases $s_j=1\text{and}{s}_{j+1}=2$ or $s_{j+6}=1\text{and}{s}_{j+5}=2$ ). We have these cases are $a_1,a_2,a_3,a_4,a_8,a_{12},a_{14}$ and comes before these cases, $s_{j-1}=4$ or comes after these cases $s_{j+7}=4$ , i.e., if $s_j=1,s_{j+1}=2$ then $s_{j-1}=4$ and if $s_{j+6}=1,s_{j+5}=2$ then $s_{j+7}=4$ .

Case 2: $s_{j+1}=3,s_{j+1}=4$ and these are the 8 remaining cases. We will study these cases after rejecting isomorphism cases when there is two cases or more, where $\left(s_j,\cdots ,s_{j+6}\right)=\left(s_{j+6},\cdots ,s_j\right)$ , then we will study only one case. We have 8 cases as follows:

$\begin{array}{l}{a}_5:\left(1,3,1,3,1,4,1\right),a_6:\left(1,3,1,3,2,2,2\right),a_7:\left(1,3,1,3,2,3,1\right),a_9:\left(1,3,1,4,1,3,1\right),\\ a_{10}:\left(1,3,2,2,2,2,2\right),a_{11}:\left(1,3,2,2,2,3,1\right),a_{13}:\left(1,3,2,3,1,3,1\right),a_{15}:\left(1,4,1,3,1,3,1\right).\end{array}$

We note that two cases $a_5,a_{15}$ are similar where one of them is contrary to the other one, so we study the case $a_5$ . Also, two cases $a_7,a_{13}$ are similar, so we study the case $a_7$ . Then we study these cases: $a_5,a_6,\text{}\text{}{a}_7,a_9,a_{10},a_{11}$ . □

Notice 3.2. We note that all the possible cases in Result 3.1, do not begin or end with 3 or 4 and it do not begin or end with $s_j+s_{j+1}\ge 5$ or $s_{j+5}+s_{j+6}\ge 5$ such that $s_j=2$ or $s_{j+6}=2$ , and $s_{j+1}=3$ or $s_{j+5}=3$ . Thus implies that if $s_j=2,s_{j+1}=3$ ,

then ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}\ge 15$ . Also, we note cases $a_5,a_6,a_7$ are beginning with (1, 3, 1, 3), but from

Lemma 3.4, we get $s_{j-1}=4$ . Now, remains our three cases for studying by the following lemma are:

$a_9:\left(1,3,1,4,1,3,1\right),a_{10}:\left(1,3,2,2,2,2,2\right),a_{11}:\left(1,3,2,2,2,3,1\right).$ □

Result 3.2. If $s_{j+1}=3,s_j=1$ where $k_j\cap s=\left\{\left(1,j\right)\right\}$ or $k_j\cap s=\left\{\left(2,j\right)\right\}$ then $s_{j-1}=4$ , also for $k_j\cap s=\left\{\left(4,j\right)\right\}$ or $k_j\cap s=\left\{\left(5,j\right)\right\}$ because it are similar to two cases $k_j\cap s=\left\{\left(2,j\right)\right\}$ or $k_j\cap s=\left\{\left(1,j\right)\right\}$ , respectively. □

Lemma 3.7. If ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}=14$ , such that $s_{j+5}=3,s_{j+6}=1$ , then ${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}\ge 15$ . Furthermore, if ${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}=15$ then ${\displaystyle \underset{j+14}{\overset{j+20}{\sum }}{s}_j}\ge 15$ .

Proof. By Result 3.2, if $k_{j+6}\cap s=\left\{\left(1,j+6\right)\right\}$ , $k_{j+6}\cap s=\left\{\left(2,j+6\right)\right\}$ ,

$k_{j+6}\cap s=\left\{\left(4,j+6\right)\right\}$ or $k_{j+6}\cap s=\left\{\left(5,j+6\right)\right\}$ then $s_{j+7}=4$ . From Lemma 3.5, we

get ${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}\ge 16$ . Assume $k_{j+6}\cap s=\left\{\left(3,j+6\right)\right\}$ then we have two cases for $k_{j+5}\cap s$ :

Case 1. $k_{j+5}\cap s=\left\{\left(1,j+5\right),\left(3,j+5\right),\left(5,j+5\right)\right\}$ . Then $s_{j+7}=4$ , by lemma 3.5,

${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}\ge 16$ .

Case 2. $k_{j+5}\cap s=\left\{\left(1,j+5\right),\left(2,j+5\right),\left(5,j+5\right)\right\}$ or

$k_{j+5}\cap s=\left\{\left(1,j+5\right),\left(4,j+5\right),\left(5,j+5\right)\right\}$ and both cases are similar, so we will consider

the first case. We have $3\le s_{j+7}\le 4$ then by Lemma 3.5, ${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}\ge 15$ . If $s_{j+7}=4$ then ${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}\ge 16$ . Assume $s_{j+7}=3$ , if ${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}\ge 16$ the proof is finish. Assume ${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}=15$

then we have cases $s_{j+8}=1,2,3\text{or}4$ .

Subcase 2.1. If $s_{j+8}=4$ then $s_{j+9}\ge 1$ . This implies that

${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}\ge 3+4+1+{\displaystyle \underset{j+10}{\overset{j+13}{\sum }}{s}_j}=8+8=16$

{By Lemma 3.5, ${\displaystyle \underset{j}{\overset{j+3}{\sum }}{s}_j}\ge 8$ }.

Subcase 2.2. If $s_{j+8}=3$ then ${\displaystyle \underset{j+9}{\overset{j+13}{\sum }}{s}_j}\ge 9$ . If ${\displaystyle \underset{j+9}{\overset{j+13}{\sum }}{s}_j}>9$ then ${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}\ge 16$ . Assume that ${\displaystyle \underset{j+9}{\overset{j+13}{\sum }}{s}_j}=9$ then we have only one case $\left(s_{j+9},\cdots ,s_{j+13}\right)=\left(1,3,1,3,1\right)$ or $\left(s_{j+9},\cdots ,s_{j+13}\right)=\left(1,2,3,2,1\right)$ . For any case we have $s_{j+8}=4$ . So, we get ${\displaystyle \underset{j+9}{\overset{j+13}{\sum }}{s}_j}>9$ . Which implies that ${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}\ge 16$ .

Subcase 2.3. If $s_{j+8}=1$ then $s_{j+9}=4$ {because the case

$\left(s_{j+5},s_{j+6},s_{j+7},s_{j+8},s_{j+9}\right)=\left(3,1,3,1,3\right)$ is not possible, by Lemma 3.3}. Then

${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}\ge 3+1+4+{\displaystyle \underset{j+10}{\overset{j+13}{\sum }}{s}_j}\ge 8+8=16$ .

Subcase 2.4. If $s_{j+8}=2$ then $s_{j+7}=3,s_{j+8}=2$ , we have the following cases:

2.4.1. $s_{j+9}\ge 3$ then ${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}\ge 3+2+3+{\displaystyle \underset{j+10}{\overset{j+13}{\sum }}{s}_j}\ge 8+8=16$ .

2.4.2. $s_{j+9}\ne 1$ {because there is only one case for $\left(s_{j+7},s_{j+8},s_{j+9}\right)=\left(3,2,1\right)$ such that

$\left\{K_{j+7}\cup K_{j+8}\cup K_{j+9}\right\}\cap S=\left\{\left(2,j+7\right),\left(3,j+7\right),\left(4,j+7\right),\left(1,j+8\right),\left(5,j+8\right),\left(3,j+9\right)\right\}$

But according to distribution vertices $k_{j+5}\cap S$ and $k_{j+6}\cap S$ we have

$\begin{array}{l}{k}_{j+5}\cap 7\\ \ne \left\{\left(2,j+7\right),\left(3,j+7\right),\left(4,j+7\right)\right\}\end{array}$ .

2.4.3. $s_{j+9}=2$ then $s_{j+7}+s_{j+8}+s_{j+9}=7$ . This implies that

$\left(s_{j+7},s_{j+8},s_{j+9}\right)=\left(3,2,2\right)$ . We will study the cases that leads to ${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}=15$ , i.e., ${\displaystyle \underset{j+10}{\overset{j+13}{\sum }}{s}_j}=8$ , {because the cases which leads to ${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}\ge 16$ the proof will be done}. Now,

we have the fixed case $\left(s_{j+7},s_{j+8},s_{j+9}\right)=\left(3,2,2\right)$ We will consider the vertices $k_{j+10}\cap S$ which imply the following:

2.4.3.1. If $s_{j+10}=4$ then $\left(3,2,2,4,s_{j+11},s_{j+12},s_{j+13}\right),$ this implies that ${\displaystyle \underset{j+11}{\overset{j+13}{\sum }}{s}_j}=4$

and $\left(s_{j+11},s_{j+12},s_{j+13}\right)=\left(1,2,1\right)$ is not possible.

2.4.3.2. If $s_{j+10}=3$ then $\left(3,2,2,3,s_{j+11},s_{j+12},s_{j+13}\right)$ and ${\displaystyle \underset{j+11}{\overset{j+13}{\sum }}{s}_j}=5$ which imply

that $\left(s_{j+11},s_{j+12},s_{j+13}\right)=\left(2,1,2\right),\left(2,2,1\right),\left(1,2,2\right)$ or (1, 3, 1), and the only possible case is (1, 3, 1). Thus implies that $\left(s_{j+7},\cdots ,s_{j+13}\right)=\left(3,2,2,3,1,3,1\right)$ . By Lemma 3.4 and

Lemma 3.5 is $s_{j+14}=4$ , these implies that ${\displaystyle \underset{j+14}{\overset{j+20}{\sum }}{s}_j}\ge 16$ .

2.4.3.3. If $s_{j+10}=2$ then $\left(3,2,2,2,s_{j+11},s_{j+12},s_{j+13}\right)$ , i.e., ${\displaystyle \underset{j+11}{\overset{j+13}{\sum }}{s}_j}=6$ . We have

$s_{j+11}\ne 1$ {because the case $\left(2,2,1\right)$ is not possible}. Then we have the following cases for $s_{j+11},s_{j+12},s_{j+13}$ :

1). If $s_{j+11}=4$ then $s_{j+12}=1$ and $s_{j+13}=1$ , but the case $\left(4,1,1\right)$ is not possible.

2). If $s_{j+11}=3$ and $s_{j+12}=1$ then $s_{j+13}=2$ , also the case $\left(3,1,2\right)$ is not possible.

3). If $s_{j+11}=3$ , $s_{j+12}=2$ and $s_{j+13}=1$ then $\left(s_j,\cdots ,s_{j+6}\right)=\left(3,2,2,2,3,2,1\right)$ which

gets $s_{j+7}=4$ and ${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}\ge 16$ .

4). If $s_{j+11}=2$ and $s_{j+12}=2$ then $s_{j+13}=2$ , but the case $\left(3,2,2,2,2,2,2\right)$ is not possible. If $s_{j+11}=2$ , $s_{j+12}=3$ and $s_{j+13}=1$ then we gets

$\left(s_j,\cdots ,s_{j+6}\right)=\left(3,2,2,2,2,3,1\right)$ During the proof of Lemma, we notice that if $s_j=3$

and $s_{j+1}=1$ , then ${\displaystyle \underset{j+2}{\overset{j+8}{\sum }}{s}_j}\ge 15$ . This complete the proof. □

Result 3.3. Based on the Lemma 3.6, and the other Lemmas and results precede it.

We see that when we have case of ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}=14$ , then the only case that comes after it, is ${\displaystyle \underset{j+7}{\overset{j+13}{\sum }}{s}_j}=15$ such that $\left(s_{j+7},\cdots ,s_{j+13}\right)=\left(3,2,2,2,2,3,1\right)$ which continues in the same

way or it is followed by 7 columns contain 16 vertices from S {by Lemma 3.6,

${\displaystyle \underset{j+14}{\overset{j+20}{\sum }}{s}_j}\ge 15$ , because $s_{j+12}=3$ , $s_{j+13}=1$ }. When this case is repeated then ${\displaystyle \underset{j=n-6}{\overset{n}{\sum }}{s}_j}\ge 15$ and then when the case ${\displaystyle \underset{j}{\overset{j+6}{\sum }}{s}_j}=14$ it is necessary, the case ${\displaystyle \underset{j+6+q}{\overset{j+6+q-1+7r}{\sum }}{s}_j}\ge 16$ exists as well {where $j+6+q-1+7r\le n$ } these implies that ${\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}\ge \lceil \frac{15n}{7}\rceil$ then

${\gamma }_2\left(P_5\times P_n\right)={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}\ge 2n+\lceil \frac{n}{7}\rceil$ . □

Lemma 3.8. Let S be 2-dominating set for ${{\rm P}}_5\times {{\rm P}}_n$ then:

1) $s_1\ge 2\text{and}{s}_1+s_2\ge 4\left(s_{n-1}+s_n\ge 4,s_n\ge 2\right)$ .

2) If $s_1+s_2=4$ then $s_1+s_2+s_3=8$ ( $s_{n-1}+s_n=4$ then $s_{n-2}+s_{n-1}+s_n=8$ ).

3) $s_1+s_2+s_3\ge 6\left(s_{n-2}+s_{n-1}+s_n\ge 6\right)$ .

4) ${\displaystyle \underset{j=1}{\overset{4}{\sum }}{s}_j}\ge 9\left({\displaystyle \underset{j=n-3}{\overset{n}{\sum }}{s}_j}\ge 9\right)$ .

5) ${\displaystyle \underset{j=1}{\overset{5}{\sum }}{s}_j}\ge 10\left({\displaystyle \underset{j=n-4}{\overset{n}{\sum }}{s}_j}\ge 10\right)$ and if ${\displaystyle \underset{j=1}{\overset{5}{\sum }}{s}_j}=10$ then ${\displaystyle \underset{j=1}{\overset{6}{\sum }}{s}_j}\ge 14$ , also if ${\displaystyle \underset{j=n-4}{\overset{n}{\sum }}{s}_j}=10$ then ${\displaystyle \underset{j=n-5}{\overset{n}{\sum }}{s}_j}\ge 14$

6) ${\displaystyle \underset{j=1}{\overset{6}{\sum }}{s}_j}\ge 13\left({\displaystyle \underset{j=n-5}{\overset{n}{\sum }}{s}_j}\ge 13\right)$ .

7) ${\displaystyle \underset{j=1}{\overset{7}{\sum }}{s}_j}\ge 15\left({\displaystyle \underset{j=n-6}{\overset{n}{\sum }}{s}_j}\ge 15\right)$ .

8) If $s_1+s_2=5$ then either ${\displaystyle \underset{j=1}{\overset{5}{\sum }}{s}_j}\ge 11$ or ${\displaystyle \underset{j=1}{\overset{6}{\sum }}{s}_j}\ge 14$ , also if $s_{n-1}+s_n=5$ then either ${\displaystyle \underset{j=n-4}{\overset{n}{\sum }}{s}_j}\ge 11$ or ${\displaystyle \underset{j=n-5}{\overset{n}{\sum }}{s}_j}\ge 14$ .

Proof. The study of dominating sequence $\left(s_1,s_2,\cdots ,s_n\right)$ is the same as the study of the dominating sequence $\left(s_n,s_{n-1},\cdots ,s_1\right)$ , so we study one case $\left(s_1,s_2,\cdots ,s_n\right)$ . Also, the

study of ${\displaystyle \underset{j=1}{\overset{r}{\sum }}{s}_j}$ is the same as the study of ${\displaystyle \underset{j=n-r+1}{\overset{n}{\sum }}{s}_j}$ .

1) We have $s_1\ge 2$ , if $s_1=2$ then $s_2\ge 3$ thus, $s_1+s_2\ge 5$ if $s_1\ge 3$ then $s_2\ge 1\left(1\le s_j\le 4\right)$ these implies that $s_1+s_2\ge 4$ .

2) If $s_1+s_2=4$ , then we have only one the case $k_1\cap s=\left\{\left(1,1\right),\left(3,1\right),\left(5,1\right)\right\}$ these implies that $k_2\cap s=\left\{\left(3,2\right)\right\}$ and $s_3=4$ then $s_1+s_2+s_3=8$ .

3) If $s_1+s_2\ge 5$ , then ${\displaystyle \underset{j=1}{\overset{3}{\sum }}{s}_j}\ge 6$ {because $1\le s_j\le 4$ } and if $s_1+s_2=4$ then by 2, is ${\displaystyle \underset{j=1}{\overset{3}{\sum }}{s}_j}=8$ .

4) If $s_1+s_2=4$ then ${\displaystyle \underset{j=1}{\overset{4}{\sum }}{s}_j}=8$ these implies that ${\displaystyle \underset{j=1}{\overset{4}{\sum }}{s}_j}\ge 9$ and if $s_1+s_2\ge 6$ then ${\displaystyle \underset{j=1}{\overset{4}{\sum }}{s}_j}\ge 9$ {because $s_3+s_4\ge 3$ }. Assume that $s_1+s_2=5$ , then we have three cases:

4.1) $s_1=2,s_2=3$ then $s_3+s_4\ge 4$ , because the case $\left(s_2,s_3,s_4\right)=\left(3,1,2\right)$ is not possible. Also the case $\left(s_2,s_3,s_4\right)=\left(3,2,1\right)$ is not possible, else when $k_2\cap s=\left\{\left(2,2\right),\left(3,2\right),\left(4,2\right)\right\}$ and this is not possible.

4.2) $s_1=3,s_2=2$ then $s_3+s_4\ge 4$ because the cases $\left(s_2,s_3,s_4\right)=\left(2,2,1\right)$ , $\left(s_2,s_3,s_4\right)=\left(2,1,2\right)$ are not possible.

4.3) $s_1=4,s_2=1$ then $s_3+s_4\ge 4$ , because the cases $\left(s_1,s_2,s_3,s_4\right)=\left(4,1,2,1\right)$ ,

$\left(s_1,s_2,s_3,s_4\right)=\left(4,1,2,2\right)$ are not possible. Thus implies that we have ${\displaystyle \underset{j=1}{\overset{4}{\sum }}{s}_j}\ge 9$ .

5) By Lemma 3.4, we have two cases for ${\displaystyle \underset{j=1}{\overset{4}{\sum }}{s}_j}=9$ and these two cases are

$\left(1,2,3,2,1\right),\left(1,3,1,3,1\right)$ , furthermore these cannot be shown here because $s_1\ge 2$ . Thus

implies that we ${\displaystyle \underset{j=1}{\overset{5}{\sum }}{s}_j}\ge 10$ .

6). If $s_1+s_2\ge 5$ then ${\displaystyle \underset{j=1}{\overset{6}{\sum }}{s}_j}=s_1+s_2+{\displaystyle \underset{j=3}{\overset{6}{\sum }}{s}_j}\ge 5+8=13$ .

(where by Lemma 3.5, we have ${\displaystyle \underset{j}{\overset{j+3}{\sum }}{s}_j}\ge 8$ ). Let $s_1+s_2=4$ then ${\displaystyle \underset{j=1}{\overset{3}{\sum }}{s}_j}=8$ these implies that ${\displaystyle \underset{j=1}{\overset{6}{\sum }}{s}_j}\ge 8+{\displaystyle \underset{j=4}{\overset{6}{\sum }}{s}_j}$ . Thus implies that ${\displaystyle \underset{j=1}{\overset{6}{\sum }}{s}_j}\ge 8+5=13$ {because ${\displaystyle \underset{j}{\overset{j+2}{\sum }}{s}_j}\ge 5$ }.

7) If $s_1\ge 3$ then from Lemma 3.5, ${\displaystyle \underset{j=1}{\overset{7}{\sum }}{s}_j}\ge 15$ . Let $s_1=2$ {because $s_1>1$ } then $s_2\ge 3$ . This implies that ${\displaystyle \underset{j=1}{\overset{7}{\sum }}{s}_j}\ge 15$ {by Notice 3.2}.

8) If $s_1+s_2=5$ then either ${\displaystyle \underset{j=1}{\overset{5}{\sum }}{s}_j}\ge 11$ or ${\displaystyle \underset{j=1}{\overset{6}{\sum }}{s}_j}\ge 14$ . We have $s_1+s_2=5$ , then

we have three

cases:

8.1) $s_1=4,s_2=1$ , then $s_3+s_4+s_5\ge 7$ because the cases

$\left(s_1,s_2,s_3,s_4,s_5\right)=\left(4,1,2,2,2\right),\left(4,1,3,2,1\right),\left(4,1,2,3,1\right)\text{or}\left(4,1,3,1,2\right)$ are not possible.

Thus implies that ${\displaystyle \underset{j=1}{\overset{5}{\sum }}{s}_j}\ge 11$ .

8.2) $s_1=2,s_2=3$ , then ${\displaystyle \underset{j=1}{\overset{5}{\sum }}{s}_j}\ge 10$ and if ${\displaystyle \underset{j=1}{\overset{5}{\sum }}{s}_j}=10$ then

$\left(s_1,s_2,s_3,s_4,s_5\right)=\left(2,3,1,3,1\right)$ . By Lemma 3.4, $s_6=4$ . Thus implies that ${\displaystyle \underset{j=1}{\overset{6}{\sum }}{s}_j}\ge 14$ .

8.3) $s_1=3,s_2=2$ , then $\left(s_1,s_2,s_3,s_4,s_5\right)$ it has minimal numerals in the following cases $\left(s_1,s_2,s_3,s_4,s_5\right)=\left(3,2,2,2,2\right),\left(3,2,1,4,1\right)\text{or}\left(3,2,3,1,3\right)$ and for the case

$\left(s_3,s_4,s_5\right)=\left(1,3,1\right)$ is not compatible with the case $\left(s_1,s_2\right)=\left(3,2\right).$ Thus implies that

${\displaystyle \underset{j=1}{\overset{5}{\sum }}{s}_j}\ge 11$ . This completes the proof. □

Theorem 3.5.

${\gamma }_2\left(P_5\times P_n\right)=\{\begin{array}{l}2n+\lceil \frac{n}{7}\rceil :n\equiv 1,2,3,5\left(\mathrm{mod}7\right),\\ 2n+\lceil \frac{n}{7}\rceil +1:n\equiv 0,4,6\left(\mathrm{mod}7\right).\end{array}$

Proof. By Result 3.3, we have ${\gamma }_2\left(p_5\times p_n\right)={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}\ge \lceil \frac{15n}{7}\rceil$ . By Theorem 3.4, we get ${\gamma }_2\left(p_5\times p_n\right)=2n+\lceil \frac{n}{7}\rceil :n\equiv 1,2,3,5\left(\mathrm{mod}7\right).$

Now, for $n\equiv 0,4,6\left(\mathrm{mod}7\right)$ , by Theorem 3.4, we have ${\gamma }_2\left(p_5\times p_n\right)\le 2n+\lceil \frac{n}{7}\rceil +1$ . From Result 3.3, we have ${\gamma }_2\left(p_5\times p_n\right)\ge 2n+\lceil \frac{n}{7}\rceil$ . We will study the cases:

1) $n\equiv 0\left(\mathrm{mod}7\right)$ . We have ${\gamma }_2\left(p_5\times p_n\right)={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}$ . So, we consider the following:

a) $s_1+s_2=4$ then $s_1+s_2+s_3=8$ and by Lemma 3.8,

$\begin{array}{l}{\gamma }_2\left(p_5\times p_n\right)={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}=s_1+s_2+s_3+{\displaystyle \underset{j=4}{\overset{n-4}{\sum }}{s}_j}+{\displaystyle \underset{j=n-3}{\overset{n}{\sum }}{s}_j}\ge 8+2\left(n-2\right)+\frac{n-7}{7}+9,\\ {\gamma }_2\left(p_5\times p_n\right)\ge 17+2n-14+\frac{n-7}{7}=2n+\frac{n+14}{7}=2n+\lceil \frac{n}{7}\rceil +2\ge 2n+\lceil \frac{n}{7}\rceil +1.\end{array}$

b) $s_1+s_2\ge 5$ if $s_1+s_2\ge 6$ then

$\begin{array}{c}{\gamma }_2\left(p_5\times p_n\right)={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}=s_1+s_2+{\displaystyle \underset{j=3}{\overset{n-5}{\sum }}{s}_j}+{\displaystyle \underset{j=n-4}{\overset{n}{\sum }}{s}_j}\ge 6+2\left(n-7\right)+\frac{n-7}{7}+10\\ =2n+\frac{n-7+14}{7}=2n+\lceil \frac{n}{7}\rceil +1.\end{array}$

Let $s_1+s_2=5$ then by Lemma 3.8, ${\displaystyle \underset{j=1}{\overset{5}{\sum }}{s}_j}\ge 11$ or ${\displaystyle \underset{j=1}{\overset{6}{\sum }}{s}_j}\ge 14$ . If ${\displaystyle \underset{j=1}{\overset{5}{\sum }}{s}_j}\ge 11$ then

$\begin{array}{c}{\gamma }_2\left(p_5\times p_n\right)={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}={\displaystyle \underset{j=1}{\overset{5}{\sum }}{s}_j}+{\displaystyle \underset{j=6}{\overset{n-2}{\sum }}{s}_j}+s_{n-1}+s_n\ge 11+2\left(n-7\right)+\frac{n-7}{7}+5\\ =2n+\frac{n}{7}+1=2n+\lceil \frac{n}{7}\rceil +1.\end{array}$

{where the case $s_{n-1}+s_n=4$ is the same as $s_1+s_2=4$ }. If ${\displaystyle \underset{j=1}{\overset{5}{\sum }}{s}_j}<11$ then by Lemma 3.8, we have ${\displaystyle \underset{j=1}{\overset{6}{\sum }}{s}_j}\ge 14$

$\begin{array}{c}{\gamma }_2\left(p_5\times p_n\right)={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}=s_1+s_2+{\displaystyle \underset{j=3}{\overset{n-5}{\sum }}{s}_j}+{\displaystyle \underset{j=n-4}{\overset{n}{\sum }}{s}_j}\ge 6+2\left(n-7\right)+\frac{n-7}{7}+10\\ =2n+\frac{n-7+14}{7}=2n+\lceil \frac{n}{7}\rceil +1.\end{array}$

And with Theorem 3.4, we get ${\gamma }_2\left(p_5\times p_n\right)=2n+\lceil \frac{n}{7}\rceil +1:n\equiv 0\left(\mathrm{mod}7\right)$ .

2) When $n\equiv 4\left(\mathrm{mod}7\right)$ we have two cases:

a) $s_1+s_2=4$ . Thus implies that $s_1+s_2+s_3=8$ then

$\begin{array}{c}{\gamma }_2\left(p_5\times p_n\right)={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}={\displaystyle \underset{j=1}{\overset{3}{\sum }}{s}_j}+{\displaystyle \underset{j=4}{\overset{n-1}{\sum }}{s}_j}+s_n\ge 8+\frac{15\left(n-4\right)}{7}+2\\ =2n+\frac{n+10}{7}=2n+\lceil \frac{n}{7}\rceil +1.\end{array}$

b) $s_1+s_2\ge 5$ {where $s_{n-1}+s_n\ge 5$ } then

$\begin{array}{c}{\gamma }_2\left(p_5\times p_n\right)={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}=s_1+s_2+{\displaystyle \underset{j=3}{\overset{n-2}{\sum }}{s}_j}+s_{n-1}+s_n\ge 5+2\left(n-4\right)+\frac{n-4}{7}+5\\ =2n+\frac{n+10}{7}=2n+\lceil \frac{n}{7}\rceil +1.\end{array}$

Then by Theorem 3.4, we get ${\gamma }_2\left(p_5\times p_n\right)=2n+\lceil \frac{n}{7}\rceil +1:n\equiv 4\left(\mathrm{mod}7\right)$ .

3) $n\equiv 6\left(\mathrm{mod}7\right)$ . We have two cases:

a) If $s_1+s_2=4$ then $s_1+s_2+s_3=8$ . Thus implies that

$\begin{array}{c}{\gamma }_2\left(p_5\times p_n\right)={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}=s_1+s_2+s_3+{\displaystyle \underset{j=4}{\overset{n-3}{\sum }}{s}_j}+s_{n-2}+s_{n-1}+s_n\ge 8+2\left(n-6\right)+\frac{n-6}{7}+6\\ =2n+\lceil \frac{n}{7}\rceil +1.\end{array}$

b) If $s_1+s_2\ge 5$ then $s_{n-1}+s_n\ge 5$ . Thus implies that

$\begin{array}{c}{\gamma }_2\left(p_5\times p_n\right)={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_j}={\displaystyle \underset{j=1}{\overset{4}{\sum }}{s}_j}+{\displaystyle \underset{j=5}{\overset{n-2}{\sum }}{s}_j}+s_{n-1}+s_n\ge 9+2\left(n-6\right)+\frac{n-6}{7}+5\\ =2n+\frac{n+8}{7}=2n+\lceil \frac{n}{7}\rceil +1.\end{array}$

By Theorem 3.4, we get ${\gamma }_2\left(p_5\times p_n\right)=2n+\lceil \frac{n}{7}\rceil +1:n\equiv 6\left(\mathrm{mod}7\right).$ Finally, we get

${\gamma }_2\left(p_5\times p_n\right)=\{\begin{array}{l}2n+\lceil \frac{n}{7}\rceil :n\equiv 1,2,3,5\left(\mathrm{mod}7\right),\hfill \\ 2n+\lceil \frac{n}{7}\rceil +1:n\equiv 0,4,6\left(\mathrm{mod}7\right).\hfill \end{array}$

This completes the proof. □

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Mohan, J.J. and Kelkar, I. (2012) Restrained 2-Domination Number of Complete Grid Graphs. International Journal of Applied Mathematics and Computation, 4, 352-358.
[2]	Fink, J.F. and Jacobson, M.S. (1985) n-Domination in graphs, in: Graph Theory with Application to Algorithms and Computer Science. John Wiley and Sons, New York, 282-300.
[3]	Fink, J.F. and Jacobson, M.S. (1985) On n-Domination, n-Dependence and Forbidden Subgraphs. In: Graph Theory with Application to Algorithms and Computer Science, John Wiley and Sons, New York, 301-311.
[4]	Haynes, T.W., Hedetniemi, S.T., Henning, M.A. and Slater, P.J. (2003) H-Forming Sets in Graphs. Discrete Mathematics, 262, 159-169. https://doi.org/10.1016/S0012-365X(02)00496-X
[5]	Haynes, T.W., Hedetniemi, S.T. and Slater, P.J. (1998) Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York.
[6]	Hansberg, A. and Volkmann, L. (2009) Upper Bounds on the k-Domination Number and the k-Roman Domination Number. Discrete Applied Mathematics, 157, 1634-1639. https://doi.org/10.1016/j.dam.2008.10.011
[7]	Cockayne, E.J., Gamble, B. and Shepherd, B. (1985) An Upper Bound for the k-Domination Number of a Graph. Journal of Graph Theory, 9, 533-534. https://doi.org/10.1002/jgt.3190090414
[8]	Blidia, M., Chellali, M. and Volkmann, L. (2006) Some Bounds on the p-Domination Number in Trees. Discrete Mathematics, 306, 2031-2037. https://doi.org/10.1016/j.disc.2006.04.010
[9]	Favaron, O., Hansberg, A. and Volkmann, L. (2008) On k-Domination and Minimum Degree in Graphs. Journal of Graph Theory, 57, 33-40. https://doi.org/10.1002/jgt.20279
[10]	Volkmann, L. (2010) A Bound on the k-Domination Number of a Graph. Czechoslovak Mathematical Journal, 60, 77-83. https://doi.org/10.1007/s10587-010-0019-1
[11]	Shaheen, R. (2009) Bounds for the 2-Domination Number of Toroidal Grid Graphs. International Journal of Computer Mathematics, 86, 584-588. https://doi.org/10.1080/00207160701690284
[12]	Shaheen, R. (2013) On the 2-Domination Number of Cartesian Product of Two Cycles. Advances and Applications in Discrete Mathematics, 12, 83-108.