ABSTRACT

A set D of vertices of a graph G = (V, E) is called k-dominating if every vertex $v\in V-D$ is adjacent to some k vertices of D. The k-domination number of a graph G, ${\gamma }_k\left(G\right)$ , 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 \sum _{i=0}^{k-1}\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 \sum _{j=1}^n{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 \sum _{j=1}^n{s}_j}={\displaystyle \sum _{j=1}^n{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 \sum _{j=1}^n{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 \sum _{j=1}^n{s}_j}={\displaystyle \sum _{j=1}^n{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 \sum _{j=1}^n{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 \sum _{j=1}^n{s}_j}={\displaystyle \sum _{j=1}^n{s^{\prime }}_j=}{s^{\prime }}_1+{s^{\prime }}_n+{\displaystyle \sum _{j=2}^{n-1}{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 \sum _{j=1}^n{s}_j}={\displaystyle \sum _{j=1}^n{s^{\prime }}_j=}{s^{\prime }}_1+{s^{\prime }}_2+{s^{\prime }}_{n-1}+{s^{\prime }}_n+{\displaystyle \sum _{j=2}^{n-2}{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 \sum _{j=1}^n{s}_j}=$

${\displaystyle \sum _{j=1}^n{s^{\prime }}_j=}{s^{\prime }}_1+{s^{\prime }}_2+{s^{\prime }}_{n-1}+{s^{\prime }}_n+{\displaystyle \sum _{j=3}^{n-2}{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 \sum _j^{j+3}{s}_j}\ge 8$ .

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

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

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

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

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

2) By 1, we have ${\displaystyle \sum _j^{j+3}{s}_j}\ge 8$ . If ${\displaystyle \sum _j^{j+3}{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 \sum _j^{j+5}{s}_j}\ge 12$ .

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

3) We have ${\displaystyle \sum _j^{j+2}{s}_j}\ge 5$ and ${\displaystyle \sum _{j+4}^{j+6}{s}_j}\ge 5$ . If ${\displaystyle \sum _{j+4}^{j+6}{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 \sum _j^{j+3}{s}_j}=8$ , this implies that

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

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

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

Lemma 3.6. If ${\displaystyle \sum _j^{j+6}{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 \sum _j^{j+6}{s}_j}\ge 15$ . Now, we must study the case $s_j=s_{j+6}=2$ . We have ${\displaystyle \sum _{j+2}^{j+5}{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 \sum _j^{j+6}{s}_j}\ge 15$ , this is a contradiction with ${\displaystyle \sum _j^{j+6}{s}_j}=14$ . Now, we have ${\displaystyle \sum _j^{j+5}{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 \sum _{j+3}^{j+6}{s}_j}\ge 8$ then ${\displaystyle \sum _j^{j+6}{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 \sum _{j+4}^{j+5}{s}_j}\ge 4$ (because two cases $\left(1,2,2\right),\left(2,1,2\right)$ are not possible). Thus implies that ${\displaystyle \sum _j^{j+6}{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 \sum _j^{j+6}{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 \sum _j^{j+6}{s}_j}\ge 15$ , because $s_{j+4}+s_{j+5}+s_{j+6}\ge 8$ , we have ${\displaystyle \sum _j^{j+3}{s}_j}\ge 8$ . Then ${\displaystyle \sum _j^{j+6}{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 \sum _j^{j+3}{s}_j}\ge 8$ . This implies that ${\displaystyle \sum _j^{j+6}{s}_j}\ge 15$ this is a contradiction.

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

Result 3.1. If ${\displaystyle \sum _j^{j+6}{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 \sum _j^{j+6}{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 \sum _j^{j+6}{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 \sum _j^{j+6}{s}_j}=14$ , such that $s_{j+5}=3,s_{j+6}=1$ , then ${\displaystyle \sum _{j+7}^{j+13}{s}_j}\ge 15$ . Furthermore, if ${\displaystyle \sum _{j+7}^{j+13}{s}_j}=15$ then ${\displaystyle \sum _{j+14}^{j+20}{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 \sum _{j+7}^{j+13}{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 \sum _{j+7}^{j+13}{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 \sum _{j+7}^{j+13}{s}_j}\ge 15$ . If $s_{j+7}=4$ then ${\displaystyle \sum _{j+7}^{j+13}{s}_j}\ge 16$ . Assume $s_{j+7}=3$ , if ${\displaystyle \sum _{j+7}^{j+13}{s}_j}\ge 16$ the proof is finish. Assume ${\displaystyle \sum _{j+7}^{j+13}{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 \sum _{j+7}^{j+13}{s}_j}\ge 3+4+1+{\displaystyle \sum _{j+10}^{j+13}{s}_j}=8+8=16$

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

Subcase 2.2. If $s_{j+8}=3$ then ${\displaystyle \sum _{j+9}^{j+13}{s}_j}\ge 9$ . If ${\displaystyle \sum _{j+9}^{j+13}{s}_j}>9$ then ${\displaystyle \sum _{j+7}^{j+13}{s}_j}\ge 16$ . Assume that ${\displaystyle \sum _{j+9}^{j+13}{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 \sum _{j+9}^{j+13}{s}_j}>9$ . Which implies that ${\displaystyle \sum _{j+7}^{j+13}{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 \sum _{j+7}^{j+13}{s}_j}\ge 3+1+4+{\displaystyle \sum _{j+10}^{j+13}{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 \sum _{j+7}^{j+13}{s}_j}\ge 3+2+3+{\displaystyle \sum _{j+10}^{j+13}{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

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 \sum _{j+7}^{j+13}{s}_j}=15$ , i.e., ${\displaystyle \sum _{j+10}^{j+13}{s}_j}=8$ , {because the cases which leads to ${\displaystyle \sum _{j+7}^{j+13}{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 \sum _{j+11}^{j+13}{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 \sum _{j+11}^{j+13}{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 \sum _{j+14}^{j+20}{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 \sum _{j+11}^{j+13}{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 \sum _{j+7}^{j+13}{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 \sum _{j+2}^{j+8}{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 \sum _j^{j+6}{s}_j}=14$ , then the only case that comes after it, is ${\displaystyle \sum _{j+7}^{j+13}{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 \sum _{j+14}^{j+20}{s}_j}\ge 15$ , because $s_{j+12}=3$ , $s_{j+13}=1$ }. When this case is repeated then ${\displaystyle \sum _{j=n-6}^n{s}_j}\ge 15$ and then when the case ${\displaystyle \sum _j^{j+6}{s}_j}=14$ it is necessary, the case ${\displaystyle \sum _{j+6+q}^{j+6+q-1+7r}{s}_j}\ge 16$ exists as well {where $j+6+q-1+7r\le n$ } these implies that ${\displaystyle \sum _{j=1}^n{s}_j}\ge \lceil \frac{15n}{7}\rceil$ then

${\gamma }_2\left(P_5\times P_n\right)={\displaystyle \sum _{j=1}^n{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 \sum _{j=1}^4{s}_j}\ge 9\left({\displaystyle \sum _{j=n-3}^n{s}_j}\ge 9\right)$ .

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

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

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

8) If $s_1+s_2=5$ then either ${\displaystyle \sum _{j=1}^5{s}_j}\ge 11$ or ${\displaystyle \sum _{j=1}^6{s}_j}\ge 14$ , also if $s_{n-1}+s_n=5$ then either ${\displaystyle \sum _{j=n-4}^n{s}_j}\ge 11$ or ${\displaystyle \sum _{j=n-5}^n{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 \sum _{j=1}^r{s}_j}$ is the same as the study of ${\displaystyle \sum _{j=n-r+1}^n{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 \sum _{j=1}^3{s}_j}\ge 6$ {because $1\le s_j\le 4$ } and if $s_1+s_2=4$ then by 2, is ${\displaystyle \sum _{j=1}^3{s}_j}=8$ .

4) If $s_1+s_2=4$ then ${\displaystyle \sum _{j=1}^4{s}_j}=8$ these implies that ${\displaystyle \sum _{j=1}^4{s}_j}\ge 9$ and if $s_1+s_2\ge 6$ then ${\displaystyle \sum _{j=1}^4{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 \sum _{j=1}^4{s}_j}\ge 9$ .

5) By Lemma 3.4, we have two cases for ${\displaystyle \sum _{j=1}^4{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 \sum _{j=1}^5{s}_j}\ge 10$ .

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

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

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

8) If $s_1+s_2=5$ then either ${\displaystyle \sum _{j=1}^5{s}_j}\ge 11$ or ${\displaystyle \sum _{j=1}^6{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 \sum _{j=1}^5{s}_j}\ge 11$ .

8.2) $s_1=2,s_2=3$ , then ${\displaystyle \sum _{j=1}^5{s}_j}\ge 10$ and if ${\displaystyle \sum _{j=1}^5{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 \sum _{j=1}^6{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 \sum _{j=1}^5{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 \sum _{j=1}^n{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 \sum _{j=1}^n{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 \sum _{j=1}^n{s}_j}=s_1+s_2+s_3+{\displaystyle \sum _{j=4}^{n-4}{s}_j}+{\displaystyle \sum _{j=n-3}^n{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 \sum _{j=1}^n{s}_j}=s_1+s_2+{\displaystyle \sum _{j=3}^{n-5}{s}_j}+{\displaystyle \sum _{j=n-4}^n{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 \sum _{j=1}^5{s}_j}\ge 11$ or ${\displaystyle \sum _{j=1}^6{s}_j}\ge 14$ . If ${\displaystyle \sum _{j=1}^5{s}_j}\ge 11$ then

$\begin{array}{c}{\gamma }_2\left(p_5\times p_n\right)={\displaystyle \sum _{j=1}^n{s}_j}={\displaystyle \sum _{j=1}^5{s}_j}+{\displaystyle \sum _{j=6}^{n-2}{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 \sum _{j=1}^5{s}_j}<11$ then by Lemma 3.8, we have ${\displaystyle \sum _{j=1}^6{s}_j}\ge 14$

$\begin{array}{c}{\gamma }_2\left(p_5\times p_n\right)={\displaystyle \sum _{j=1}^n{s}_j}=s_1+s_2+{\displaystyle \sum _{j=3}^{n-5}{s}_j}+{\displaystyle \sum _{j=n-4}^n{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 \sum _{j=1}^n{s}_j}={\displaystyle \sum _{j=1}^3{s}_j}+{\displaystyle \sum _{j=4}^{n-1}{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 \sum _{j=1}^n{s}_j}=s_1+s_2+{\displaystyle \sum _{j=3}^{n-2}{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 \sum _{j=1}^n{s}_j}=s_1+s_2+s_3+{\displaystyle \sum _{j=4}^{n-3}{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 \sum _{j=1}^n{s}_j}={\displaystyle \sum _{j=1}^4{s}_j}+{\displaystyle \sum _{j=5}^{n-2}{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. □

Cite this paper

Shaheen, R., Mah- fud, S. and Almanea, K. (2017) On the 2-Domination Number of Complete Grid Graphs. Open Journal of Discrete Mathematics, 7, 32-50. http://dx.doi.org/10.4236/ojdm.2017.71004

References