On the 2-Domination Number of Complete Grid Graphs
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 Pm × Pn for m = 1, 2, 3, 4, 5 and arbitrary n. These results were shown an error in the paper .

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 $\mathrm{min}\left\{|D|: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×H\right)=V\left(G\right)×V\left(H\right)$ , where two vertices $\left({v}_{1},{v}_{2}\right)$ , $\left({u}_{1},{u}_{2}\right)\in G×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}×{P}_{n}=\left\{\left(i,j\right):1\le i\le m,1\le j\le n\right\}$ . The jth column of ${P}_{m}×{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}×{P}_{n}$ , then we put ${W}_{j}=D\cap {K}_{j}$ . Let ${s}_{j}=|{W}_{j}|$ . 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 $|V|$ and $|E|$ to order and size of graph G, respectively.

2. Notation and Terminology

Fink and Jacobson   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)=|V|$ .

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

Theorem 2.1  . 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  . If T is a tree, then ${\gamma }_{2}\left(T\right)\ge \frac{|T|+1}{2}$ .

In  , Hansberg and Volkmann, proved the following theorem.

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

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

Cockayne, et al.  , 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  . Let G be a graph with minimum degree at least k, then

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

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

Theorem 2.5  . 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{|V|+|S|}{2}$ .

Favaron, et al.  , gave new upper bounds of ${\gamma }_{k}\left(G\right)$ .

Corollary 2.6  . 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}|V|.$

In  , 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  . For every nontrivial tree, ${\gamma }_{2}\left(T\right)\ge {\gamma }_{t}\left(T\right)$ .

Also, Volkmann  gave the important following result.

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

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

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

Theorem 2.9  .

1) ${\gamma }_{2}\left({C}_{n}\right)=⌈n/2⌉$ .

2) ${\gamma }_{2}\left({C}_{3}×{C}_{n}\right)=n:n\equiv 0\left(\mathrm{mod}3\right)$ ,

${\gamma }_{2}\left({C}_{3}×{C}_{n}\right)=n+1:n\equiv 1,2\left(\mathrm{mod}3\right)$ .

3) ${\gamma }_{2}\left({C}_{4}×{C}_{n}\right)=n+⌈n/2⌉:n\equiv 0,3,5\left(\mathrm{mod}8\right)$ ,

${\gamma }_{2}\left({C}_{4}×{C}_{n}\right)=n+⌈n/2⌉+1:n\equiv 1,2,4,6,7\left(\mathrm{mod}14\right)$ .

4) ${\gamma }_{2}\left({C}_{5}×{C}_{n}\right)=2n$ .

5) ${\gamma }_{2}\left({C}_{6}×{C}_{n}\right)=2n:n\equiv 0\left(\mathrm{mod}3\right)$ ,

${\gamma }_{2}\left({C}_{6}×{C}_{n}\right)=2n+2:n\equiv 1,2\left(\mathrm{mod}3\right)$ .

6) ${\gamma }_{2}\left({C}_{7}×{C}_{n}\right)=⌈5n/2⌉:n\equiv 0,3,11\left(\mathrm{mod}14\right)$ ,

${\gamma }_{2}\left({C}_{7}×{C}_{n}\right)=⌈5n/2⌉+1:n\equiv 5,6,7,8,9,10\left(\mathrm{mod}14\right)$ ,

${\gamma }_{2}\left({C}_{7}×{C}_{n}\right)=⌈5n/2⌉+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}×{P}_{n}$ for m = 1, 2, 3, 4, 5 and arbitrary n. These results were shown an error in the paper  . 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  ,

${\gamma }_{2}\left({P}_{n}\right)=⌈\left(n+1\right)/2⌉\cdot {\gamma }_{2}\left({P}_{2}×{P}_{n}\right)=n\cdot {\gamma }_{2}\left({P}_{3}×{P}_{n}\right)=2n-⌈n/2⌉\cdot {\gamma }_{2}\left({P}_{4}×{P}_{n}\right)=2n.$

${\gamma }_{2}\left({P}_{5}×{P}_{n}\right)=3n-⌈n/2⌉\cdot {\gamma }_{2}\left({P}_{2k+1}×{P}_{n}\right)=\left(k+1\right)n-⌈n/2⌉.$

$\begin{array}{l}{\gamma }_{2}\left({P}_{m}×{P}_{n}\right)=⌈m/2⌉n-⌈n/2⌉:m\equiv 1\left(\mathrm{mod}2\right),\\ {\gamma }_{2}\left({P}_{m}×{P}_{n}\right)=⌈m/2⌉n:m\equiv 0\left(\mathrm{mod}2\right).\end{array}$

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

${\gamma }_{2}\left({P}_{n}\right)=⌈\left(n+1\right)/2⌉\cdot {\gamma }_{2}\left({P}_{2}×{P}_{n}\right)=n\cdot {\gamma }_{2}\left({P}_{3}×{P}_{n}\right)=n+⌈n/3⌉.$

$\begin{array}{l}{\gamma }_{2}\left({P}_{4}×{P}_{n}\right)=2n-⌊n/4⌋:n\equiv 3,7\left(\mathrm{mod}8\right),\\ {\gamma }_{2}\left({P}_{4}×{P}_{n}\right)=2n-⌊n/4⌋+1:n\equiv 0,1,2,4,5,6\left(\mathrm{mod}8\right).\end{array}$

$\begin{array}{l}{\gamma }_{2}\left({P}_{5}×{P}_{n}\right)=2n+⌈n/7⌉:n\equiv 1,2,3,5\left(\mathrm{mod}7\right),\\ {\gamma }_{2}\left({P}_{5}×{P}_{n}\right)=2n+⌈n/7⌉+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}×{P}_{n}$ and then we establish that D is a minimum 2-domi- nating set of ${P}_{m}×{P}_{n}$ for several values of m and arbitrary n. Definitely we have ${\gamma }_{2}\left({P}_{m}×{P}_{n}\right)=|D|$ .

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}×{P}_{n}=\left\{\left(i,\text{}j\right):1\le i\le m,1\le j\le n\right\}$ . The jth column ${P}_{m}×{P}_{n}$ is ${K}_{j}=\left\{\left(i,\text{}j\right):i=1,\cdots ,m\right\}$ .

If D is a 2-dominating set for ${P}_{m}×{P}_{n}$ then we put ${W}_{j}=D\cap {K}_{j}$ . Let ${s}_{j}=|{W}_{j}|$ . 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 ⌈m/3⌉$ . 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}+4{s}_{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}×{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 $⌊m/4⌋\le {s}_{j}\le ⌈3m/4⌉$ .

Proof. Let D be a minimum 2-dominating set for ${P}_{m}×{P}_{n}$ with 2-dominating sequence $\left({s}_{1},{s}_{2}-,\cdots ,{s}_{n}\right)$ . Assume that for some j, sj 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}×{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 $|W|=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 D1 is a 2-dominating set for ${P}_{m}×{P}_{n}$ with $|D|=|{D}_{1}|$ . 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 ⌈3m/4⌉$ , for all 1 ≤ j ≤ n.

To prove the lower bound, we suppose that $|{K}_{j}\cap D|$ is be a maximum, i.e., ${s}_{j}=⌈3m/4⌉$ . Then for each $\left(i,j\right)\notin D$ , we have

$|\left\{\left(i-1,j+1\right),\left(i,j+1\right),\left(i+1,j+1\right)\right\}\cap D|\ge 1$ . When ${s}_{j}=⌈3m/4⌉$ , there at must $m-⌈3m/4⌉=⌊m/4⌋$ vertices does not in ${K}_{j}\cap D$ . This implies that ${s}_{j+1}\ge ⌊m/4⌋$ . So, the same as for ${s}_{j-1}\ge ⌊m/4⌋$ . □

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 $⌊m/4⌋\le {s}_{j}\le ⌈3m/4⌉$ , for all $j=1,2,\cdots ,n$ .

Lemma 3.2. ${\gamma }_{2}\left({P}_{n}\right)=⌈\frac{n+1}{2}⌉$ .

Figure 1. Modify D.

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

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

Let D1 be a minimum 2-dominating set for Pn 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 D1,

this implies that ${x}_{2j-1}\in {D}_{1}$ for $2\le j\le ⌊\frac{n}{2}⌋$ . Thus implies that

$|{D}_{1}|\ge 2+⌊\frac{n}{2}⌋-1=⌈\frac{n+1}{2}⌉$ . We result that ${\gamma }_{2}\left({P}_{n}\right)=⌈\frac{n+1}{2}⌉$ . □

Theorem 3.1. ${\gamma }_{2}\left({P}_{2}×{P}_{n}\right)=n$ .

Proof. Let a set $D=\left\{\left(1,2k-1\right):1\le k\le ⌈\frac{n}{2}⌉\right\}\cup \left\{\left(2,2k\right):1\le k\le ⌊\frac{n}{2}⌋\right\}$ .

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

We can check that D is 2-dominating set for ${P}_{2}×{P}_{n}$ , see Figure 2. Let D1 be a minimum 2-dominating set for ${P}_{2}×{P}_{n}$ with dominating sequence $\left({s}_{1},\cdots ,{s}_{n}\right)$ . If ${s}_{i}\ge 1$ for all

$j=1,\cdots ,n$ , then $|{D}_{1}|=\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

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

By (1), (2) and (3) is ${\gamma }_{2}\left({P}_{2}×{P}_{n}\right)=n$ . This completes the proof of the theorem. □

Theorem 3.2. ${\gamma }_{2}\left({P}_{3}×{P}_{n}\right)=n+⌈\frac{n}{3}⌉$ .

Proof. Let $\begin{array}{l}D=\left\{\left(2,3k-2\right):1\le k\le ⌈\frac{n}{3}⌉\right\}\cup \left\{\left(2,3k\right):1\le k\le ⌊\frac{n}{3}⌋\right\}\\ \text{}\cup \left\{\left(1,3k-1\right),\left(3,3k-1\right):1\le k\le ⌈\frac{n-1}{3}⌉\right\}\end{array}$ .

Figure 2. A 2-dominating set for P2 × P10.

$\begin{array}{l}{D}^{\prime }=\left\{\left(1,3k-2\right),\left(3,3k-2\right):1\le k\le ⌈\frac{n}{3}⌉\right\}\cup \left\{\left(2,3k-1\right):1\le k\le ⌈\frac{n-1}{3}⌉\right\}\\ \text{}\cup \left\{\left(2,3k\right):1\le k\le ⌊\frac{n}{3}⌋\right\}\end{array}$ .

We have $|D|=n+⌈\frac{n}{3}⌉$ and $|{D}^{\prime }|=n+⌈\frac{n}{3}⌉$ . (4)

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

D is 2-dominating set for ${P}_{3}×{P}_{n}$ when $n=0,2\left(\mathrm{mod}3\right)$ , (see Figure 3, for P3 × P14).

${D}^{\prime }$ is 2-dominating set for ${P}_{3}×{P}_{n}$ when $n=1\left(\mathrm{mod}3\right)$ , (see Figure 4, for P3 × P10).

Let D1 be a minimum 2-dominating set for ${P}_{3}×{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 , 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 $|{D}_{1}|=\underset{j=1}{\overset{n}{\sum }}{s}_{j}\ge n+⌈\frac{n}{3}⌉$ . (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 $|{D}_{1}|=\underset{j=1}{\overset{n}{\sum }}{s}_{j}=\underset{j=1}{\overset{n}{\sum }}{s}_{j}^{\}$ . 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

$|{D}_{1}|=\underset{j=1}{\overset{n}{\sum }}{{s}^{\prime }}_{j}\ge n+⌈\frac{n}{3}⌉$ . (6)

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

Theorem 3.3. ${\gamma }_{2}\left({P}_{4}×{P}_{n}\right)=\left\{\begin{array}{l}2n-⌊\frac{n}{4}⌋:n\equiv 3,7\left(\mathrm{mod}8\right),\\ 2n-⌊\frac{n}{4}⌋+1:n\equiv 0,1,2,4,5,6\left(\mathrm{mod}8\right).\end{array}$

Figure 3. A 2-dominating set for P3 × P14.

Figure 4. A 2-dominating set for P3 × P10.

Proof. Let a set D defined as follows:

$\begin{array}{l}D=\left\{\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 ⌈\frac{n-1}{4}⌉\right\}\\ \text{}\cup \left\{\left(2,8k-5\right);1\le k\le ⌈\frac{n-2}{8}⌉\right\}\\ \text{}\cup \left\{\left(1,8k-4\right),\left(3,8k-4\right),\left(4,8k-4\right);1\le k\le ⌈\frac{n-3}{8}⌉\right\}\\ \text{}\cup \left\{\left(2,8k-3\right);1\le k\le ⌈\frac{n-4}{8}⌉\right\}\cup \left\{\left(3,8k-1\right);1\le k\le ⌈\frac{n-6}{8}⌉\right\}\\ \text{}\cup \left\{\left(1,8k\right),\left(2,8k\right),\left(4,8k\right);1\le k\le ⌈\frac{n-7}{8}⌉\right\}\cup \left\{\left(3,8k+1\right);1\le k\le ⌊\frac{n-1}{8}⌋\right\}\right\}\end{array}$

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

We can check that the following sets are 2-dominating set for ${P}_{4}×{P}_{n}$ (see Figure 5, for ${P}_{4}×{P}_{11}$ ) as indicated:

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

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

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

We have

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

Let D1 be a minimum 2-dominating set for ${P}_{4}×{P}_{n}$ with 2-dominating sequence $\left({s}_{1},\cdots ,{s}_{n}\right)$ we shall show that

$|{D}_{1}|=\left\{\begin{array}{l}2n-⌊\frac{n}{4}⌋:n\equiv 3,7\left(\mathrm{mod}8\right),\\ 2n-⌊\frac{n}{4}⌋+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 P4 × P11.

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

$|{D}_{1}|=\underset{j=1}{\overset{n}{\sum }}{s}_{j}=\underset{j=1}{\overset{n}{\sum }}{{s}^{\prime }}_{j}={{s}^{\prime }}_{1}+{{s}^{\prime }}_{n}+\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

$|{D}_{1}|=\underset{j=1}{\overset{n}{\sum }}{s}_{j}=\underset{j=1}{\overset{n}{\sum }}{{s}^{\prime }}_{j}={{s}^{\prime }}_{1}+{{s}^{\prime }}_{2}+{{s}^{\prime }}_{n-1}+{{s}^{\prime }}_{n}+\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,\text{}{s}_{n}=3$ and ${s}_{2}\ge 2,\text{}{s}_{n-1}\ge 1\text{or}{s}_{1}=3,\text{}{s}_{n}=2$ and ${s}_{2}\ge 1,\text{}{s}_{n-1}\ge 2$ . Two cases are similar by symmetry. We consider the first case:

${s}_{1}=2,\text{}{s}_{2}\ge 2$ and ${s}_{n}=3,\text{}{s}_{n-1}\ge 1$ , this implies that

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

$|{D}_{1}|=\underset{j=1}{\overset{n}{\sum }}{s}_{j}=\underset{j=1}{\overset{n}{\sum }}{{s}^{\prime }}_{j}={{s}^{\prime }}_{1}+{{s}^{\prime }}_{2}+{{s}^{\prime }}_{n-1}+{{s}^{\prime }}_{n}+\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-⌊\frac{n}{4}⌋=\frac{7n}{4}+\frac{3}{4}$ for $n\equiv 3,7\left(\mathrm{mod}8\right)$ ,

$2n-⌊\frac{n}{4}⌋+1=\left\{\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

$|{D}_{1}|\ge \left\{\begin{array}{l}2n-⌊\frac{n}{4}⌋;n\equiv 3,7\left(\mathrm{mod}8\right),\\ 2n-⌊\frac{n}{4}⌋+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}×{P}_{n}\right)=2n-⌊\frac{n}{4}⌋:n\equiv 3,7\left(\mathrm{mod}8\right),\\ {\gamma }_{2}\left({P}_{4}×{P}_{n}\right)=2n-⌊\frac{n}{4}⌋+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}×{P}_{n}\right)=\left\{\begin{array}{l}2n+⌈\frac{n}{7}⌉:n\equiv 1,2,3,5\left(\mathrm{mod}7\right),\\ 2n+⌈\frac{n}{7}⌉+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\{\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\}\\ \text{}\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\}\\ \text{}\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\}\\ \text{}\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\right\}\end{array}$

We can check that the following sets are 2-dominating set for ${P}_{5}×{P}_{n}$ (see Figure 6, for ${P}_{5}×{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+⌈\frac{n}{7}⌉$ and

${\gamma }_{2}\left({P}_{5}×{P}_{n}\right)\le \left\{\begin{array}{l}2n+⌈\frac{n}{7}⌉:n\equiv 1,2,3,5\left(\mathrm{mod}7\right),\\ 2n+⌈\frac{n}{7}⌉+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 P5 × P23.

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) $\underset{j}{\overset{j+3}{\sum }}{s}_{j}\ge 8$ .

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

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

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

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

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

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

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

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

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

$\underset{j}{\overset{j+3}{\sum }}{s}_{j}\ge 9$ . Then $\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 $\underset{j+4}{\overset{j+6}{\sum }}{s}_{j}\ge 6$ then $\underset{j}{\overset{j+6}{\sum }}{s}_{j}=\underset{j}{\overset{j+3}{\sum }}{s}_{j}+\underset{j+4}{\overset{j+6}{\sum }}{s}_{j}\ge 8+6=14$ .

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

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

Lemma 3.6. If $\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

$\underset{j}{\overset{j+6}{\sum }}{s}_{j}\ge 15$ . Now, we must study the case ${s}_{j}={s}_{j+6}=2$ . We have $\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 $\underset{j}{\overset{j+6}{\sum }}{s}_{j}\ge 15$ , this is a contradiction with $\underset{j}{\overset{j+6}{\sum }}{s}_{j}=14$ . Now, we have $\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 $\underset{j+3}{\overset{j+6}{\sum }}{s}_{j}\ge 8$ then $\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 $\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 $\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 $\underset{j}{\overset{j+6}{\sum }}{s}_{j}\ge 15$ , this is a contradiction.

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

we will study case ${s}_{j+2}=2,\text{}{s}_{j+4}=4$ then ${s}_{j+5}\ge 1,$ if ${s}_{j+5}\ge 2$ , then $\underset{j}{\overset{j+6}{\sum }}{s}_{j}\ge 15$ , because ${s}_{j+4}+{s}_{j+5}+{s}_{j+6}\ge 8$ , we have $\underset{j}{\overset{j+3}{\sum }}{s}_{j}\ge 8$ . Then $\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 $\underset{j}{\overset{j+3}{\sum }}{s}_{j}\ge 8$ . This implies that $\underset{j}{\overset{j+6}{\sum }}{s}_{j}\ge 15$ this is a contradiction.

Finally, we get if $\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 $\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),\text{}{a}_{2}:\left(1,2,3,2,2,2,2\right),\text{}{a}_{3}:\left(1,2,3,2,2,3,1\right),\\ {a}_{4}:\left(1,2,3,3,1,3,1\right),\text{}{a}_{5}:\left(1,3,1,3,1,4,1\right),\text{}{a}_{6}:\left(1,3,1,3,2,2,2\right),\\ {a}_{7}:\left(1,3,1,3,2,3,1\right),\text{}{a}_{8}:\left(1,3,1,3,3,2,1\right),\text{}{a}_{9}:\left(1,3,1,4,1,3,1\right),\\ {a}_{10}:\left(1,3,2,2,2,2,2\right),\text{}{a}_{11}:\left(1,3,2,2,2,3,1\right),\text{}{a}_{12}:\left(1,3,2,2,3,2,1\right),\\ {a}_{13}:\left(1,3,2,3,1,3,1\right),\text{}{a}_{14}:\left(1,4,1,2,3,2,1\right),\text{}{a}_{15}:\left(1,4,1,3,1,3,1\right).\end{array}$

It is 15 cases (where ${s}_{j}=1$ with $\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,\text{}{s}_{j+1}=2$ then ${s}_{j-1}=4$ and if ${s}_{j+6}=1,\text{}{s}_{j+5}=2$ then ${s}_{j+7}=4$ .

Case 2: ${s}_{j+1}=3,\text{}{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),\text{}{a}_{6}:\left(1,3,1,3,2,2,2\right),\text{}{a}_{7}:\left(1,3,1,3,2,3,1\right),\text{}{a}_{9}:\left(1,3,1,4,1,3,1\right),\\ {a}_{10}:\left(1,3,2,2,2,2,2\right),\text{}{a}_{11}:\left(1,3,2,2,2,3,1\right),\text{}{a}_{13}:\left(1,3,2,3,1,3,1\right),\text{}{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,\text{}{s}_{j+1}=3$ ,

then $\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),\text{}{a}_{10}:\left(1,3,2,2,2,2,2\right),\text{}{a}_{11}:\left(1,3,2,2,2,3,1\right).$

Result 3.2. If ${s}_{j+1}=3,\text{}{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 $\underset{j}{\overset{j+6}{\sum }}{s}_{j}=14$ , such that ${s}_{j+5}=3,\text{}{s}_{j+6}=1$ , then $\underset{j+7}{\overset{j+13}{\sum }}{s}_{j}\ge 15$ . Furthermore, if $\underset{j+7}{\overset{j+13}{\sum }}{s}_{j}=15$ then $\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 $\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,

$\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, $\underset{j+7}{\overset{j+13}{\sum }}{s}_{j}\ge 15$ . If ${s}_{j+7}=4$ then $\underset{j+7}{\overset{j+13}{\sum }}{s}_{j}\ge 16$ . Assume ${s}_{j+7}=3$ , if $\underset{j+7}{\overset{j+13}{\sum }}{s}_{j}\ge 16$ the proof is finish. Assume $\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

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

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

Subcase 2.2. If ${s}_{j+8}=3$ then $\underset{j+9}{\overset{j+13}{\sum }}{s}_{j}\ge 9$ . If $\underset{j+9}{\overset{j+13}{\sum }}{s}_{j}>9$ then $\underset{j+7}{\overset{j+13}{\sum }}{s}_{j}\ge 16$ . Assume that $\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 $\underset{j+9}{\overset{j+13}{\sum }}{s}_{j}>9$ . Which implies that $\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

$\underset{j+7}{\overset{j+13}{\sum }}{s}_{j}\ge 3+1+4+\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,\text{}{s}_{j+8}=2$ , we have the following cases:

2.4.1. ${s}_{j+9}\ge 3$ then $\underset{j+7}{\overset{j+13}{\sum }}{s}_{j}\ge 3+2+3+\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 $\underset{j+7}{\overset{j+13}{\sum }}{s}_{j}=15$ , i.e., $\underset{j+10}{\overset{j+13}{\sum }}{s}_{j}=8$ , {because the cases which leads to $\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 $\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 $\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 $\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., $\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 $\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 $\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 $\underset{j}{\overset{j+6}{\sum }}{s}_{j}=14$ , then the only case that comes after it, is $\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,

$\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 $\underset{j=n-6}{\overset{n}{\sum }}{s}_{j}\ge 15$ and then when the case $\underset{j}{\overset{j+6}{\sum }}{s}_{j}=14$ it is necessary, the case $\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 $\underset{j=1}{\overset{n}{\sum }}{s}_{j}\ge ⌈\frac{15n}{7}⌉$ then

${\gamma }_{2}\left({P}_{5}×{P}_{n}\right)=\underset{j=1}{\overset{n}{\sum }}{s}_{j}\ge 2n+⌈\frac{n}{7}⌉$ . □

Lemma 3.8. Let S be 2-dominating set for ${Ρ}_{5}×{Ρ}_{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) $\underset{j=1}{\overset{4}{\sum }}{s}_{j}\ge 9\left(\underset{j=n-3}{\overset{n}{\sum }}{s}_{j}\ge 9\right)$ .

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

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

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

8) If ${s}_{1}+{s}_{2}=5$ then either $\underset{j=1}{\overset{5}{\sum }}{s}_{j}\ge 11$ or $\underset{j=1}{\overset{6}{\sum }}{s}_{j}\ge 14$ , also if ${s}_{n-1}+{s}_{n}=5$ then either $\underset{j=n-4}{\overset{n}{\sum }}{s}_{j}\ge 11$ or $\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 $\underset{j=1}{\overset{r}{\sum }}{s}_{j}$ is the same as the study of $\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 $\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 $\underset{j=1}{\overset{3}{\sum }}{s}_{j}=8$ .

4) If ${s}_{1}+{s}_{2}=4$ then $\underset{j=1}{\overset{4}{\sum }}{s}_{j}=8$ these implies that $\underset{j=1}{\overset{4}{\sum }}{s}_{j}\ge 9$ and if ${s}_{1}+{s}_{2}\ge 6$ then $\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,\text{}{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,\text{}{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,\text{}{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 $\underset{j=1}{\overset{4}{\sum }}{s}_{j}\ge 9$ .

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

6). If ${s}_{1}+{s}_{2}\ge 5$ then $\underset{j=1}{\overset{6}{\sum }}{s}_{j}={s}_{1}+{s}_{2}+\underset{j=3}{\overset{6}{\sum }}{s}_{j}\ge 5+8=13$ .

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

7) If ${s}_{1}\ge 3$ then from Lemma 3.5, $\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 $\underset{j=1}{\overset{7}{\sum }}{s}_{j}\ge 15$ {by Notice 3.2}.

8) If ${s}_{1}+{s}_{2}=5$ then either $\underset{j=1}{\overset{5}{\sum }}{s}_{j}\ge 11$ or $\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,\text{}{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 $\underset{j=1}{\overset{5}{\sum }}{s}_{j}\ge 11$ .

8.2) ${s}_{1}=2,\text{}{s}_{2}=3$ , then $\underset{j=1}{\overset{5}{\sum }}{s}_{j}\ge 10$ and if $\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 $\underset{j=1}{\overset{6}{\sum }}{s}_{j}\ge 14$ .

8.3) ${s}_{1}=3,\text{}{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

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

Theorem 3.5.

${\gamma }_{2}\left({P}_{5}×{P}_{n}\right)=\left\{\begin{array}{l}2n+⌈\frac{n}{7}⌉:n\equiv 1,2,3,5\left(\mathrm{mod}7\right),\\ 2n+⌈\frac{n}{7}⌉+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}×{p}_{n}\right)=\underset{j=1}{\overset{n}{\sum }}{s}_{j}\ge ⌈\frac{15n}{7}⌉$ . By Theorem 3.4, we get ${\gamma }_{2}\left({p}_{5}×{p}_{n}\right)=2n+⌈\frac{n}{7}⌉: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}×{p}_{n}\right)\le 2n+⌈\frac{n}{7}⌉+1$ . From Result 3.3, we have ${\gamma }_{2}\left({p}_{5}×{p}_{n}\right)\ge 2n+⌈\frac{n}{7}⌉$ . We will study the cases:

1) $n\equiv 0\left(\mathrm{mod}7\right)$ . We have ${\gamma }_{2}\left({p}_{5}×{p}_{n}\right)=\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}×{p}_{n}\right)=\underset{j=1}{\overset{n}{\sum }}{s}_{j}={s}_{1}+{s}_{2}+{s}_{3}+\underset{j=4}{\overset{n-4}{\sum }}{s}_{j}+\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}×{p}_{n}\right)\ge 17+2n-14+\frac{n-7}{7}=2n+\frac{n+14}{7}=2n+⌈\frac{n}{7}⌉+2\ge 2n+⌈\frac{n}{7}⌉+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}×{p}_{n}\right)=\underset{j=1}{\overset{n}{\sum }}{s}_{j}={s}_{1}+{s}_{2}+\underset{j=3}{\overset{n-5}{\sum }}{s}_{j}+\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+⌈\frac{n}{7}⌉+1.\end{array}$

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

$\begin{array}{c}{\gamma }_{2}\left({p}_{5}×{p}_{n}\right)=\underset{j=1}{\overset{n}{\sum }}{s}_{j}=\underset{j=1}{\overset{5}{\sum }}{s}_{j}+\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+⌈\frac{n}{7}⌉+1.\end{array}$

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

$\begin{array}{c}{\gamma }_{2}\left({p}_{5}×{p}_{n}\right)=\underset{j=1}{\overset{n}{\sum }}{s}_{j}={s}_{1}+{s}_{2}+\underset{j=3}{\overset{n-5}{\sum }}{s}_{j}+\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+⌈\frac{n}{7}⌉+1.\end{array}$

And with Theorem 3.4, we get ${\gamma }_{2}\left({p}_{5}×{p}_{n}\right)=2n+⌈\frac{n}{7}⌉+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}×{p}_{n}\right)=\underset{j=1}{\overset{n}{\sum }}{s}_{j}=\underset{j=1}{\overset{3}{\sum }}{s}_{j}+\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+⌈\frac{n}{7}⌉+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}×{p}_{n}\right)=\underset{j=1}{\overset{n}{\sum }}{s}_{j}={s}_{1}+{s}_{2}+\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+⌈\frac{n}{7}⌉+1.\end{array}$

Then by Theorem 3.4, we get ${\gamma }_{2}\left({p}_{5}×{p}_{n}\right)=2n+⌈\frac{n}{7}⌉+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}×{p}_{n}\right)=\underset{j=1}{\overset{n}{\sum }}{s}_{j}={s}_{1}+{s}_{2}+{s}_{3}+\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+⌈\frac{n}{7}⌉+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}×{p}_{n}\right)=\underset{j=1}{\overset{n}{\sum }}{s}_{j}=\underset{j=1}{\overset{4}{\sum }}{s}_{j}+\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+⌈\frac{n}{7}⌉+1.\end{array}$

By Theorem 3.4, we get ${\gamma }_{2}\left({p}_{5}×{p}_{n}\right)=2n+⌈\frac{n}{7}⌉+1:n\equiv 6\left(\mathrm{mod}7\right).$ Finally, we get

${\gamma }_{2}\left({p}_{5}×{p}_{n}\right)=\left\{\begin{array}{l}2n+⌈\frac{n}{7}⌉:n\equiv 1,2,3,5\left(\mathrm{mod}7\right),\hfill \\ 2n+⌈\frac{n}{7}⌉+1:n\equiv 0,4,6\left(\mathrm{mod}7\right).\hfill \end{array}$

This completes the proof. □

Cite this paper: Shaheen, R. , Mahfud, S. and Almanea, K. (2017) On the 2-Domination Number of Complete Grid Graphs. Open Journal of Discrete Mathematics, 7, 32-50. doi: 10.4236/ojdm.2017.71004.
References

   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.

   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.

   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.

   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

   Haynes, T.W., Hedetniemi, S.T. and Slater, P.J. (1998) Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York.

   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

   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

   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

   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

   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

   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

   Shaheen, R. (2013) On the 2-Domination Number of Cartesian Product of Two Cycles. Advances and Applications in Discrete Mathematics, 12, 83-108.

Top