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

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}$ .

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

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

$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).

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

${\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-