OJDM  Vol.7 No.1 , January 2017
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].

1. Introduction

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

The Cartesian product G ´ H of two graphs G and H is the graph with vertex set V ( G × H ) = V ( G ) × V ( H ) , where two vertices ( v 1 , v 2 ) , ( u 1 , u 2 ) G × H are adjacent if and only if either v 1 u 1 E ( G ) and v 2 = u 2 or v 2 u 2 E ( H ) and v 1 = u 1 .

Let G be a path of order n with vertex set V ( G ) = { 1 , 2 , , n } . Then for two paths of order m and n respectively, we have P m × P n = { ( i , j ) : 1 i m , 1 j n } . The jth column of P m × P n is K j = { ( i , j ) : i = 1 , , m } . If D is a 2-dominating set for P m × P n , then we put W j = D K j . Let s j = | W j | . The sequence ( s 1 , s 2 , , s n ) is called a 2-dominating sequence corresponding to D. For a graph G, we refer to minimum and maximum degrees by #Math_25# and Δ ( G ) , 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 [2] [3] in 1985 to introduced the concept of multiple domination. A subset D 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 γ k ( G ) of G. Clearly, g 1 ( G ) = g ( G ) . Naturally, every k-dominating set of a graph G contains all vertices of degree less than k. Of course, every ( k + 1 ) -dominating set is also a k-dominating set and so γ k ( G ) γ k + 1 ( G ) . Moreover, the vertex set V is the only ( Δ + 1 ) -dominating set but evidently it is not a minimum D-dominating set. Thus every graph G satisfies

γ k ( G ) γ k + 1 ( G ) γ Δ ( G ) < γ Δ + 1 ( G ) = | V | .

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 2 , is an integer and G is a graph with k Δ ( G ) , then γ k ( G ) γ ( G ) + k 2 .

Theorem 2.2 [2] . If T is a tree, then γ 2 ( T ) | T | + 1 2 .

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

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

let k N . If δ + 1 ln ( δ + 1 ) 2 k , then γ k ( G ) | V | δ + 1 ( k ln ( δ + 1 ) + i = 0 k 1 δ i i ! ( δ + 1 ) k 1 ) .

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

γ k ( G ) k | V | ( k + 1 ) .

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 γ k ( G ) | V | + | S | 2 .

Favaron, et al. [9] , gave new upper bounds of γ k ( G ) .

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

an integer, then γ k ( G ) δ 2 δ + 1 k | V | .

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, γ 2 ( T ) γ t ( T ) .

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

Theorem 2.8 [10] . Let G be a graph with minimum degree δ k + 1 , then

γ k + 1 ( G ) | V | + γ k ( G ) 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) γ 2 ( C n ) = n / 2 .

2) γ 2 ( C 3 × C n ) = n : n 0 ( mod 3 ) ,

γ 2 ( C 3 × C n ) = n + 1 : n 1 , 2 ( mod 3 ) .

3) γ 2 ( C 4 × C n ) = n + n / 2 : n 0 , 3 , 5 ( mod 8 ) ,

γ 2 ( C 4 × C n ) = n + n / 2 + 1 : n 1 , 2 , 4 , 6 , 7 ( mod 14 ) .

4) γ 2 ( C 5 × C n ) = 2 n .

5) γ 2 ( C 6 × C n ) = 2 n : n 0 ( mod 3 ) ,

γ 2 ( C 6 × C n ) = 2 n + 2 : n 1 , 2 ( mod 3 ) .

6) γ 2 ( C 7 × C n ) = 5 n / 2 : n 0 , 3 , 11 ( mod 14 ) ,

γ 2 ( C 7 × C n ) = 5 n / 2 + 1 : n 5 , 6 , 7 , 8 , 9 , 10 ( mod 14 ) ,

γ 2 ( C 7 × C n ) = 5 n / 2 + 2 : n 1 , 2 , 4 , 12 , 13 ( mod 14 ) .

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] . 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] ,

γ 2 ( P n ) = ( n + 1 ) / 2 γ 2 ( P 2 × P n ) = n γ 2 ( P 3 × P n ) = 2 n n / 2 γ 2 ( P 4 × P n ) = 2 n .

γ 2 ( P 5 × P n ) = 3 n n / 2 γ 2 ( P 2 k + 1 × P n ) = ( k + 1 ) n n / 2 .

γ 2 ( P m × P n ) = m / 2 n n / 2 : m 1 ( mod 2 ) , γ 2 ( P m × P n ) = m / 2 n : m 0 ( mod 2 ) .

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

γ 2 ( P n ) = ( n + 1 ) / 2 γ 2 ( P 2 × P n ) = n γ 2 ( P 3 × P n ) = n + n / 3 .

γ 2 ( P 4 × P n ) = 2 n n / 4 : n 3 , 7 ( mod 8 ) , γ 2 ( P 4 × P n ) = 2 n n / 4 + 1 : n 0 , 1 , 2 , 4 , 5 , 6 ( mod 8 ) .

γ 2 ( P 5 × P n ) = 2 n + n / 7 : n 1 , 2 , 3 , 5 ( mod 7 ) , γ 2 ( P 5 × P n ) = 2 n + n / 7 + 1 : n 0 , 4 , 6 ( mod 7 ) .

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 γ 2 ( P m × P n ) = | D | .

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

P m × P n = { ( i , j ) : 1 i m , 1 j n } . The jth column P m × P n is K j = { ( i , j ) : i = 1 , , m } .

If D is a 2-dominating set for P m × P n then we put W j = D K j . Let s j = | W j | . The sequence ( s 1 , s 2 , , s n ) is called a 2-dominating sequence corresponding to D. Always we have s 1 , s n 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 = 2 m , then s j 1 = s j + 1 = m . In general s j 1 + 4 s j + s j + 1 2 m .

Notice 3.1.

1) The study of 2-dominating sequence ( s 1 , s 2 , , s n ) is the same as the study of the 2-dominating sequence ( s n , s n 1 , , s 1 ) .

2) If subsequence ( s j , s j + 1 , , s j + k ) is not possible, then its reverse ( s j + k , , s j + 1 , s j ) is not possible.

3) We say that two subsequences ( s j , , s j + q ) , ( s j + q + 1 , , s j + r ) are equivalent, if the sequence ( s j , , s j + q , s j + q + 1 , , s j + r ) 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 ( s 1 , s 2 , , s n ) such that, for all j = 1 , 2 , , n , is m / 4 s j 3 m / 4 .

Proof. Let D be a minimum 2-dominating set for P m × P n with 2-dominating sequence ( s 1 , s 2 , , s n ) . 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 i m and 1 j n , let W = D { ( i , j ) , ( i + 1 , j ) , ( i + 2 , j ) , ( i + 3 , j ) } . If | W | = 4 , then we define D 1 = ( D W ) { ( i , j ) , ( i + 1 , j 1 ) , ( i + 2 , j + 1 ) , ( i + 3 , j ) } , 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 3 m / 4 , for all 1 ≤ j ≤ n.

To prove the lower bound, we suppose that | K j D | is be a maximum, i.e., s j = 3 m / 4 . Then for each ( i , j ) D , we have

| { ( i 1 , j + 1 ) , ( i , j + 1 ) , ( i + 1 , j + 1 ) } D | 1 . When s j = 3 m / 4 , there at must m 3 m / 4 = m / 4 vertices does not in K j D . This implies that s j + 1 m / 4 . So, the same as for s j 1 m / 4 . □

By Lemma 3.1, always we have a minimum 2-dominating set D with 2-dominating sequence ( s 1 , s 2 , , s n ) , such that m / 4 s j 3 m / 4 , for all j = 1 , 2 , , n .

Lemma 3.2. γ 2 ( P n ) = n + 1 2 .

Figure 1. Modify D.

Proof. Let D = { ( 2 k 1 ) ; 1 k n 2 } .

We have D is a 2-dominating set of Pn for n 1 ( mod 2 ) with | D | = n + 1 2 , also D { ( n ) } is a 2-dominating set of Pn for n 0 ( mod 2 ) with | D { ( n ) } | = n + 1 2 .

Let D1 be a minimum 2-dominating set for Pn with V ( P n ) = { x 1 , x 2 , , x n } . Since x 1 x n E ( P n ) , we need to x 1 , x n D 1 , also if x j D 1 then x j 1 , x j + 1 are belong to D1,

this implies that x 2 j 1 D 1 for 2 j n 2 . Thus implies that

| D 1 | 2 + n 2 1 = n + 1 2 . We result that γ 2 ( P n ) = n + 1 2 . □

Theorem 3.1. γ 2 ( P 2 × P n ) = n .

Proof. Let a set D = { ( 1 , 2 k 1 ) : 1 k n 2 } { ( 2 , 2 k ) : 1 k n 2 } .

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 ( s 1 , , s n ) . If s i 1 for all

j = 1 , , n , then | D 1 | = j = 1 n s j n . (2)

Let s j = 0 for some j, then s j 1 = s j + 1 = 2 , also we have s 1 1 and s n 1 . Now we define a new sequence ( s 1 , , s n ) , (not necessarily a 2-dominating sequence) as follows:

For s j = 2 , if j = 1 or n, we put s j = s j 1 , s 2 = s 2 + 1 / 2 and s n 1 = s n 1 + 1 / 2 .

If j 1 or n, we put s j = s j 1 , s j 1 = s j 1 + 1 / 2 and s j + 1 = s j + 1 + 1 / 2 .

Otherwise s j = s j .

We get a sequence ( s 1 , , s n ) have property that each s j 1 with

| D | = j = 1 n s j = j = 1 n s j n . (3)

By (1), (2) and (3) is γ 2 ( P 2 × P n ) = n . This completes the proof of the theorem. □

Theorem 3.2. γ 2 ( P 3 × P n ) = n + n 3 .

Proof. Let D = { ( 2 , 3 k 2 ) : 1 k n 3 } { ( 2 , 3 k ) : 1 k n 3 } { ( 1 , 3 k 1 ) , ( 3 , 3 k 1 ) : 1 k n 1 3 } .

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

D = { ( 1 , 3 k 2 ) , ( 3 , 3 k 2 ) : 1 k n 3 } { ( 2 , 3 k 1 ) : 1 k n 1 3 } { ( 2 , 3 k ) : 1 k n 3 } .

We have | D | = n + n 3 and | D | = n + n 3 . (4)

By definition D and D we note that

D is 2-dominating set for P 3 × P n when n = 0 , 2 ( mod 3 ) , (see Figure 3, for P3 × P14).

D is 2-dominating set for P 3 × P n when n = 1 ( mod 3 ) , (see Figure 4, for P3 × P10).

Let D1 be a minimum 2-dominating set for P 3 × P n with 2-dominating sequence ( s 1 , , s n ) we have s 1 , s n 1 and

if s 1 , s n = 1 then s 2 , s n 1 2 ,

if s 1 , s n = 2 then s 2 , s n 1 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 3 ,

s j = 2 then s j 1 + s j + 1 2 ,

If no one of s j = 0 for all j, then | D 1 | = j = 1 n s j n + n 3 . (5)

Let s j = 0 ( j 1 or n) for some j, we define a sequence ( s 1 , , s n ) , (not necessarily a 2-dominating sequence ) as follows:

If s j = 3 , then we put s j = s j 1 , s j 1 = s j 1 + 1 / 2 and s j + 1 = s j + 1 + 1 / 2 , otherwise

s j = s j . We have | D 1 | = j = 1 n s j = j = 1 n s j \ . We note that the sequence ( s 1 , , s n ) have the

property if s j = 1 then s j 1 + s j + 1 3 . Thus implies that

| D 1 | = j = 1 n s j n + n 3 . (6)

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

Theorem 3.3. γ 2 ( P 4 × P n ) = { 2 n n 4 : n 3 , 7 ( mod 8 ) , 2 n n 4 + 1 : n 0 , 1 , 2 , 4 , 5 , 6 ( mod 8 ) .

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:

D = { { ( 2 , 1 ) , ( 3 , 1 ) } { ( 1 , 4 k 2 ) , ( 4 , 4 k 2 ) ; 1 k n 1 4 } { ( 2 , 8 k 5 ) ; 1 k n 2 8 } { ( 1 , 8 k 4 ) , ( 3 , 8 k 4 ) , ( 4 , 8 k 4 ) ; 1 k n 3 8 } { ( 2 , 8 k 3 ) ; 1 k n 4 8 } { ( 3 , 8 k 1 ) ; 1 k n 6 8 } { ( 1 , 8 k ) , ( 2 , 8 k ) , ( 4 , 8 k ) ; 1 k n 7 8 } { ( 3 , 8 k + 1 ) ; 1 k n 1 8 } }

D = { ( 2 , n ) } , D = { ( 3 , n ) } .

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 0 , 4 ( mod 8 ) .

D D is 2-dominating set for P 4 × P n when n 1 , 2 , 7 ( mod 8 ) .

D D is 2-dominating set for P 4 × P n when n 3 , 5 , 6 ( mod 8 ) .

We have

| D | = { 2 n n 4 1 : n 3 , 7 ( mod 8 ) , 2 n n 4 : n 1 , 2 , 5 , 6 ( mod 8 ) , 2 n n 4 + 1 : n 0 , 4 ( mod 8 ) . }

Let D1 be a minimum 2-dominating set for P 4 × P n with 2-dominating sequence ( s 1 , , s n ) we shall show that

| D 1 | = { 2 n n 4 : n 3 , 7 ( mod 8 ) , 2 n n 4 + 1 : n 0 , 1 , 2 , 4 , 5 , 6 ( mod 8 ) . }

By Lemma 3.1, we have 1 s j 3 . Thus

If s j = 1 then s j 1 + s j + 1 5 .

If s j = 2 then s j 1 + s j + 1 2 .

If s j = 3 then s j 1 + s j + 1 2 .

Also, we have s 1 , s n 2 . If s 1 , s n = 2 then s 2 , s n 1 2 , and if s 1 , s n = 3 then

Figure 5. A 2-dominating set for P4 × P11.

s 2 , s n 1 1 .

We define a new set D 1 with sequence ( s 1 , , s n ) , (not necessarily a 2-dominating

sequence) as follows: if s j 2 , let M j = s j 7 4 . Now, for j = 2 to j = n 1 , if

s j 2 , then we put

s j = s j M j , s j 1 = s j 1 + M j 2 and s j + 1 = s j + 1 + M j 2

Thus, for 3 j n 2 , we have s j 7 4 . Since if s j 2 then s j 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 14 4 = 6 4 , which implies that s j = s j + M j 1 2 + M j + 1 2 = 1 + 3 4 = 7 4 .

We have three cases:

Case 1: s 1 , s n 2 , then s 2 , s n 1 2 , these implies that s 1 s 1 + 1 8 and s n s n + 1 8 also

| D 1 | = j = 1 n s j = j = 1 n s j = s 1 + s n + j = 2 n 1 s j 2 + 1 8 + 2 + 1 8 + 7 ( n 2 ) 4 = 7 n 4 + 3 4 .

Case 2: s 1 , s n = 3 then s 2 , s n 1 2 . Thus implies that s 1 , s n = 3 and

s 2 , s n 1 1 + 1 8 . Then

| D 1 | = j = 1 n s j = j = 1 n s j = s 1 + s 2 + s n 1 + s n + j = 2 n 2 s j 3 + 1 + 1 8 + 3 + 1 + 1 8 + 7 4 = 7 n 4 + 5 4

Case 3: s 1 = 2 , s n = 3 and s 2 2 , s n 1 1 or s 1 = 3 , s n = 2 and s 2 1 , s n 1 2 . Two cases are similar by symmetry. We consider the first case:

s 1 = 2 , s 2 2 and s n = 3 , s n 1 1 , this implies that

s 1 = 2 + 1 8 , s 2 = 7 4 , s n = 3 , s n 1 = 1 + 1 8 and

| D 1 | = j = 1 n s j = j = 1 n s j = s 1 + s 2 + s n 1 + s n + j = 3 n 2 s j 2 + 1 8 + 7 4 +   3 + 1 + 1 8 + 7 4 ( n 4 ) = 7 n 4 + 1

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

2 n n 4 = 7 n 4 + 3 4 for n 3 , 7 ( mod 8 ) ,

2 n n 4 + 1 = { 7 n 4 + 1 For n 0 , 4 ( mod 8 ) , 7 n 4 + 5 4 For n 1 , 5 ( mod 8 ) , 7 n 4 + 6 4 For n 2 , 6 ( mod 8 ) ,

Thus implies that

| D 1 | { 2 n n 4 ; n 3 , 7 ( mod 8 ) , 2 n n 4 + 1 ; n 0 , 1 , 2 , 4 , 5 , 6 ( mod 8 ) , }

Finally, we get

γ 2 ( P 4 × P n ) = 2 n n 4 : n 3 , 7 ( mod 8 ) , γ 2 ( P 4 × P n ) = 2 n n 4 + 1 : n 0 , 1 , 2 , 4 , 5 , 6 ( mod 8 ) ,

This complete the proof of the theorem. □

Theorem 3.4.

γ 2 ( P 5 × P n ) = { 2 n + n 7 : n 1 , 2 , 3 , 5 ( mod 7 ) , 2 n + n 7 + 1 : n 0 , 4 , 6 ( mod 7 ) .

Proof. Let a set D defined as follows:

D = { { ( 2 , 1 ) , ( 4 , 1 ) } { ( 1 , j ) , ( 2 , j ) , ( 5 , j ) : j 2 ( mod 7 ) } { ( 3 , j ) : j 3 ( mod 7 ) } { ( 1 , j ) , ( 4 , j ) , ( 5 , j ) : j 4 ( mod 7 ) } { ( 2 , j ) , ( 3 , j ) : j 5 ( mod 7 ) } { ( 2 , j ) , ( 5 , j ) : j 6 ( mod 7 ) } { ( 1 , j ) , ( 4 , j ) : j 0 ( mod 7 ) } { ( 3 , j ) , ( 4 , j ) : j 1 ( mod 7 ) } and j 1 }

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:

{ D { K n D } } { ( 2 , n ) , ( 3 , n ) , ( 5 , n ) } : n 1 ( mod 7 ) . D { ( 2 , n ) } : n 0 , 4 ( mod 7 ) . D : n 2 ( mod 7 ) . { D { K n D } } { ( 2 , n ) , ( 4 , n ) } : n 3 , 5 ( mod 7 ) . { D { K n D } } { ( 1 , n ) , ( 3 , n ) , ( 5 , n ) } : n 6 ( mod 7 ) .

We have D 2 n + n 7 and

γ 2 ( P 5 × P n ) { 2 n + n 7 : n 1 , 2 , 3 , 5 ( mod 7 ) , 2 n + n 7 + 1 : n 0 , 4 , 6 ( mod 7 ) .

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 ( s j , s j + 1 , s j + 2 , s j + 3 , s j + 4 ) = ( 2 , 2 , 2 , 2 , 2 ) .

2) There is one case for subsequence ( s j , s j + 1 , s j + 2 , s j + 3 ) = ( 1 , 3 , 1 , 3 ) .

3) There is one case for subsequence ( s j , s j + 1 , s j + 2 , s j + 3 , s j + 4 ) = ( 1 , 3 , 1 , 3 , 1 ) .

4) There is one case for subsequence ( s j , s j + 1 , s j + 2 , s j + 3 , s j + 4 ) = ( 1 , 2 , 3 , 2 , 1 ) .

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

Lemma 3.5.

1) j j + 3 s j 8 .

2) j j + 5 s j 12 .

3) j j + 6 s j 14 .

4) If s j = 3 then j j + 6 s j 15 .

5) If s j = 4 then j j + 6 s j 16 .

Proof. 1) By Lemma 3.3, imply that j j + 3 s j 8 .

2) By 1, we have j j + 3 s j 8 . If j j + 3 s j = 8 , then we have the cases

( s j , s j + 1 , s j + 2 , s j + 3 ) = ( 1 , 2 , 3 , 2 ) , ( 1 , 3 , 1 , 3 ) , ( 1 , 3 , 2 , 2 ) , ( 1 , 4 , 1 , 2 ) , ( 2 , 2 , 2 , 2 ) .

From Lemma 3.3, we have s j + 4 + s j + 5 4 , this implies that j j + 5 s j 12 .

If j j + 4 s j 9 then s j + 4 + s j + 5 3 . This implies that j j + 6 s j 12 .

3) We have j j + 2 s j 5 and j + 4 j + 6 s j 5 . If j + 4 j + 6 s j = 5 , then there is one case

( s j + 4 , s j + 5 , s j + 6 ) = ( 1 , 3 , 1 ) (where the cases ( 1 , 2 , 1 ) , ( 1 , 2 , 2 ) are not possible). But the

case ( 1 , 3 , 1 ) is not compatible with any of the cases when j j + 3 s j = 8 , this implies that

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

j j + 3 s j 9 . Then j j + 6 s j 14 (where the case ( 1 , 3 , 1 , 3 , 1 , 3 ) is not possible). If j + 4 j + 6 s j 6 then j j + 6 s j = j j + 3 s j + j + 4 j + 6 s j 8 + 6 = 14 .

4) We have s j 3 , then from 2 is j j + 6 s j 15 .

5) We have s j 4 , then from 2 is j j + 6 s j 16 . This complete the proof of the Lemma. □

Lemma 3.6. If 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 2 . From Lemma 3.5, s j , s j + 6 < 3 , else

j j + 6 s j 15 . Now, we must study the case s j = s j + 6 = 2 . We have j + 2 j + 5 s j = 10 , by Lem-

ma 3.3, the case ( 2 , 2 , 2 , 2 , 2 , 2 ) is not possible, this implies that not all elements of the subsequence ( s j + 1 , , s j + 5 ) are equal to the value 2. If s j + 1 , s j + 2 , s j + 3 , s j + 4 , s j + 5 2

where at least one of them is equal or greater than 3, then j j + 6 s j 15 , this is a contradiction with j j + 6 s j = 14 . Now, we have j j + 5 s j = 10 , where one of the subsequence ele-

ment ( s j + 1 , , s j + 5 ) is at most equal the value 1 (where 1 s j 4 ). We consider the cases s j = 1 for j + 1 j 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 j + 3 j + 6 s j 8 then j j + 6 s j 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 3 , (because the case ( 2 , 2 , 1 ) is not possible). If s j + 1 = 3 then s j + 3 3

and we have s j + 6 = 2 then j + 4 j + 5 s j 4 (because two cases ( 1 , 2 , 2 ) , ( 2 , 1 , 2 ) are not possible). Thus implies that j j + 6 s j 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 6 :

Subcase 1: s j + 2 = s j + 4 = 3 then s j + 1 , s j + 5 2 (because two cases

( s j , s j + 1 , s j + 2 ) = ( 2 , 1 , 3 ) and ( s j + 4 , s j + 5 , s j + 6 ) = ( 3 , 1 , 2 ) are not possible). Thus implies

that j j + 6 s j 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 1 , if s j + 5 2 , then j j + 6 s j 15 , because s j + 4 + s j + 5 + s j + 6 8 , we have j j + 3 s j 8 . Then j j + 6 s j 15 , this is a contradiction).

If s j + 5 = 1 , then s j + 4 + s j + 5 + s j + 6 = 7 . We have j j + 3 s j 8 . This implies that j j + 6 s j 15 this is a contradiction.

Finally, we get if j j + 6 s j = 14 , then s j = 1 or s j + 6 = 1 . This completely the proof. □

Result 3.1. If j j + 6 s j = 14 , then from Lemma 3.6, we have the cases for subsequence

( s j , s j + 1 , s j + 2 , s j + 3 , s j + 4 , s j + 5 , s j + 6 ) :

a 1 : ( 1 , 2 , 3 , 2 , 1 , 4 , 1 ) , a 2 : ( 1 , 2 , 3 , 2 , 2 , 2 , 2 ) , a 3 : ( 1 , 2 , 3 , 2 , 2 , 3 , 1 ) , a 4 : ( 1 , 2 , 3 , 3 , 1 , 3 , 1 ) , a 5 : ( 1 , 3 , 1 , 3 , 1 , 4 , 1 ) , a 6 : ( 1 , 3 , 1 , 3 , 2 , 2 , 2 ) , a 7 : ( 1 , 3 , 1 , 3 , 2 , 3 , 1 ) , a 8 : ( 1 , 3 , 1 , 3 , 3 , 2 , 1 ) , a 9 : ( 1 , 3 , 1 , 4 , 1 , 3 , 1 ) , a 10 : ( 1 , 3 , 2 , 2 , 2 , 2 , 2 ) , a 11 : ( 1 , 3 , 2 , 2 , 2 , 3 , 1 ) , a 12 : ( 1 , 3 , 2 , 2 , 3 , 2 , 1 ) , a 13 : ( 1 , 3 , 2 , 3 , 1 , 3 , 1 ) , a 14 : ( 1 , 4 , 1 , 2 , 3 , 2 , 1 ) , a 15 : ( 1 , 4 , 1 , 3 , 1 , 3 , 1 ) .

It is 15 cases (where s j = 1 with 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 and s j + 1 = 2 or s j + 6 = 1 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 ( s j , , s j + 6 ) = ( s j + 6 , , s j ) , then we will study only one case. We have 8 cases as follows:

a 5 : ( 1 , 3 , 1 , 3 , 1 , 4 , 1 ) , a 6 : ( 1 , 3 , 1 , 3 , 2 , 2 , 2 ) , a 7 : ( 1 , 3 , 1 , 3 , 2 , 3 , 1 ) , a 9 : ( 1 , 3 , 1 , 4 , 1 , 3 , 1 ) , a 10 : ( 1 , 3 , 2 , 2 , 2 , 2 , 2 ) , a 11 : ( 1 , 3 , 2 , 2 , 2 , 3 , 1 ) , a 13 : ( 1 , 3 , 2 , 3 , 1 , 3 , 1 ) , a 15 : ( 1 , 4 , 1 , 3 , 1 , 3 , 1 ) .

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 , 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 5 or s j + 5 + s j + 6 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 j j + 6 s j 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 : ( 1 , 3 , 1 , 4 , 1 , 3 , 1 ) , a 10 : ( 1 , 3 , 2 , 2 , 2 , 2 , 2 ) , a 11 : ( 1 , 3 , 2 , 2 , 2 , 3 , 1 ) .

Result 3.2. If s j + 1 = 3 , s j = 1 where k j s = { ( 1 , j ) } or k j s = { ( 2 , j ) } then s j 1 = 4 , also for k j s = { ( 4 , j ) } or k j s = { ( 5 , j ) } because it are similar to two cases k j s = { ( 2 , j ) } or k j s = { ( 1 , j ) } , respectively. □

Lemma 3.7. If j j + 6 s j = 14 , such that s j + 5 = 3 , s j + 6 = 1 , then j + 7 j + 13 s j 15 . Furthermore, if j + 7 j + 13 s j = 15 then j + 14 j + 20 s j 15 .

Proof. By Result 3.2, if k j + 6 s = { ( 1 , j + 6 ) } , k j + 6 s = { ( 2 , j + 6 ) } ,

k j + 6 s = { ( 4 , j + 6 ) } or k j + 6 s = { ( 5 , j + 6 ) } then s j + 7 = 4 . From Lemma 3.5, we

get j + 7 j + 13 s j 16 . Assume k j + 6 s = { ( 3 , j + 6 ) } then we have two cases for k j + 5 s :

Case 1. k j + 5 s = { ( 1 , j + 5 ) , ( 3 , j + 5 ) , ( 5 , j + 5 ) } . Then s j + 7 = 4 , by lemma 3.5,

j + 7 j + 13 s j 16 .

Case 2. k j + 5 s = { ( 1 , j + 5 ) , ( 2 , j + 5 ) , ( 5 , j + 5 ) } or

k j + 5 s = { ( 1 , j + 5 ) , ( 4 , j + 5 ) , ( 5 , j + 5 ) } and both cases are similar, so we will consider

the first case. We have 3 s j + 7 4 then by Lemma 3.5, j + 7 j + 13 s j 15 . If s j + 7 = 4 then j + 7 j + 13 s j 16 . Assume s j + 7 = 3 , if j + 7 j + 13 s j 16 the proof is finish. Assume j + 7 j + 13 s j = 15

then we have cases s j + 8 = 1 , 2 , 3 or 4 .

Subcase 2.1. If s j + 8 = 4 then s j + 9 1 . This implies that

j + 7 j + 13 s j 3 + 4 + 1 + j + 10 j + 13 s j = 8 + 8 = 16

{By Lemma 3.5, j j + 3 s j 8 }.

Subcase 2.2. If s j + 8 = 3 then j + 9 j + 13 s j 9 . If j + 9 j + 13 s j > 9 then j + 7 j + 13 s j 16 . Assume that j + 9 j + 13 s j = 9 then we have only one case ( s j + 9 , , s j + 13 ) = ( 1 , 3 , 1 , 3 , 1 ) or ( s j + 9 , , s j + 13 ) = ( 1 , 2 , 3 , 2 , 1 ) . For any case we have s j + 8 = 4 . So, we get j + 9 j + 13 s j > 9 . Which implies that j + 7 j + 13 s j 16 .

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

( s j + 5 , s j + 6 , s j + 7 , s j + 8 , s j + 9 ) = ( 3 , 1 , 3 , 1 , 3 ) is not possible, by Lemma 3.3}. Then

j + 7 j + 13 s j 3 + 1 + 4 + j + 10 j + 13 s j 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 3 then j + 7 j + 13 s j 3 + 2 + 3 + j + 10 j + 13 s j 8 + 8 = 16 .

2.4.2. s j + 9 1 {because there is only one case for ( s j + 7 , s j + 8 , s j + 9 ) = ( 3 , 2 , 1 ) such that

{ K j + 7 K j + 8 K j + 9 } S = { ( 2 , j + 7 ) , ( 3 , j + 7 ) , ( 4 , j + 7 ) , ( 1 , j + 8 ) , ( 5 , j + 8 ) , ( 3 , j + 9 ) }

But according to distribution vertices k j + 5 S and k j + 6 S we have

k j + 5 7 { ( 2 , j + 7 ) , ( 3 , j + 7 ) , ( 4 , j + 7 ) } .

2.4.3. s j + 9 = 2 then s j + 7 + s j + 8 + s j + 9 = 7 . This implies that

( s j + 7 , s j + 8 , s j + 9 ) = ( 3 , 2 , 2 ) . We will study the cases that leads to j + 7 j + 13 s j = 15 , i.e., j + 10 j + 13 s j = 8 , {because the cases which leads to j + 7 j + 13 s j 16 the proof will be done}. Now,

we have the fixed case ( s j + 7 , s j + 8 , s j + 9 ) = ( 3 , 2 , 2 ) We will consider the vertices k j + 10 S which imply the following:

2.4.3.1. If s j + 10 = 4 then ( 3 , 2 , 2 , 4 , s j + 11 , s j + 12 , s j + 13 ) , this implies that j + 11 j + 13 s j = 4

and ( s j + 11 , s j + 12 , s j + 13 ) = ( 1 , 2 , 1 ) is not possible.

2.4.3.2. If s j + 10 = 3 then ( 3 , 2 , 2 , 3 , s j + 11 , s j + 12 , s j + 13 ) and j + 11 j + 13 s j = 5 which imply

that ( s j + 11 , s j + 12 , s j + 13 ) = ( 2 , 1 , 2 ) , ( 2 , 2 , 1 ) , ( 1 , 2 , 2 ) or (1, 3, 1), and the only possible case is (1, 3, 1). Thus implies that ( s j + 7 , , s j + 13 ) = ( 3 , 2 , 2 , 3 , 1 , 3 , 1 ) . By Lemma 3.4 and

Lemma 3.5 is s j + 14 = 4 , these implies that j + 14 j + 20 s j 16 .

2.4.3.3. If s j + 10 = 2 then ( 3 , 2 , 2 , 2 , s j + 11 , s j + 12 , s j + 13 ) , i.e., j + 11 j + 13 s j = 6 . We have

s j + 11 1 {because the case ( 2 , 2 , 1 ) 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 ( 4 , 1 , 1 ) is not possible.

2). If s j + 11 = 3 and s j + 12 = 1 then s j + 13 = 2 , also the case ( 3 , 1 , 2 ) is not possible.

3). If s j + 11 = 3 , s j + 12 = 2 and s j + 13 = 1 then ( s j , , s j + 6 ) = ( 3 , 2 , 2 , 2 , 3 , 2 , 1 ) which

gets s j + 7 = 4 and j + 7 j + 13 s j 16 .

4). If s j + 11 = 2 and s j + 12 = 2 then s j + 13 = 2 , but the case ( 3 , 2 , 2 , 2 , 2 , 2 , 2 ) is not possible. If s j + 11 = 2 , s j + 12 = 3 and s j + 13 = 1 then we gets

( s j , , s j + 6 ) = ( 3 , 2 , 2 , 2 , 2 , 3 , 1 ) During the proof of Lemma, we notice that if s j = 3

and s j + 1 = 1 , then j + 2 j + 8 s j 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 j j + 6 s j = 14 , then the only case that comes after it, is j + 7 j + 13 s j = 15 such that ( s j + 7 , , s j + 13 ) = ( 3 , 2 , 2 , 2 , 2 , 3 , 1 ) which continues in the same

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

j + 14 j + 20 s j 15 , because s j + 12 = 3 , s j + 13 = 1 }. When this case is repeated then j = n 6 n s j 15 and then when the case j j + 6 s j = 14 it is necessary, the case j + 6 + q j + 6 + q 1 + 7 r s j 16 exists as well {where j + 6 + q 1 + 7 r n } these implies that j = 1 n s j 15 n 7 then

γ 2 ( P 5 × P n ) = j = 1 n s j 2 n + n 7 . □

Lemma 3.8. Let S be 2-dominating set for Ρ 5 × Ρ n then:

1) s 1 2 and s 1 + s 2 4 ( s n 1 + s n 4 , s n 2 ) .

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 6 ( s n 2 + s n 1 + s n 6 ) .

4) j = 1 4 s j 9 ( j = n 3 n s j 9 ) .

5) j = 1 5 s j 10 ( j = n 4 n s j 10 ) and if j = 1 5 s j = 10 then j = 1 6 s j 14 , also if j = n 4 n s j = 10 then j = n 5 n s j 14

6) j = 1 6 s j 13 ( j = n 5 n s j 13 ) .

7) j = 1 7 s j 15 ( j = n 6 n s j 15 ) .

8) If s 1 + s 2 = 5 then either j = 1 5 s j 11 or j = 1 6 s j 14 , also if s n 1 + s n = 5 then either j = n 4 n s j 11 or j = n 5 n s j 14 .

Proof. The study of dominating sequence ( s 1 , s 2 , , s n ) is the same as the study of the dominating sequence ( s n , s n 1 , , s 1 ) , so we study one case ( s 1 , s 2 , , s n ) . Also, the

study of j = 1 r s j is the same as the study of j = n r + 1 n s j .

1) We have s 1 2 , if s 1 = 2 then s 2 3 thus, s 1 + s 2 5 if s 1 3 then s 2 1 ( 1 s j 4 ) these implies that s 1 + s 2 4 .

2) If s 1 + s 2 = 4 , then we have only one the case k 1 s = { ( 1 , 1 ) , ( 3 , 1 ) , ( 5 , 1 ) } these implies that k 2 s = { ( 3 , 2 ) } and s 3 = 4 then s 1 + s 2 + s 3 = 8 .

3) If s 1 + s 2 5 , then j = 1 3 s j 6 {because 1 s j 4 } and if s 1 + s 2 = 4 then by 2, is j = 1 3 s j = 8 .

4) If s 1 + s 2 = 4 then j = 1 4 s j = 8 these implies that j = 1 4 s j 9 and if s 1 + s 2 6 then j = 1 4 s j 9 {because s 3 + s 4 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 4 , because the case ( s 2 , s 3 , s 4 ) = ( 3 , 1 , 2 ) is not possible. Also the case ( s 2 , s 3 , s 4 ) = ( 3 , 2 , 1 ) is not possible, else when k 2 s = { ( 2 , 2 ) , ( 3 , 2 ) , ( 4 , 2 ) } and this is not possible.

4.2) s 1 = 3 , s 2 = 2 then s 3 + s 4 4 because the cases ( s 2 , s 3 , s 4 ) = ( 2 , 2 , 1 ) , ( s 2 , s 3 , s 4 ) = ( 2 , 1 , 2 ) are not possible.

4.3) s 1 = 4 , s 2 = 1 then s 3 + s 4 4 , because the cases ( s 1 , s 2 , s 3 , s 4 ) = ( 4 , 1 , 2 , 1 ) ,

( s 1 , s 2 , s 3 , s 4 ) = ( 4 , 1 , 2 , 2 ) are not possible. Thus implies that we have j = 1 4 s j 9 .

5) By Lemma 3.4, we have two cases for j = 1 4 s j = 9 and these two cases are

( 1 , 2 , 3 , 2 , 1 ) , ( 1 , 3 , 1 , 3 , 1 ) , furthermore these cannot be shown here because s 1 2 . Thus

implies that we j = 1 5 s j 10 .

6). If s 1 + s 2 5 then j = 1 6 s j = s 1 + s 2 + j = 3 6 s j 5 + 8 = 13 .

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

7) If s 1 3 then from Lemma 3.5, j = 1 7 s j 15 . Let s 1 = 2 {because s 1 > 1 } then s 2 3 . This implies that j = 1 7 s j 15 {by Notice 3.2}.

8) If s 1 + s 2 = 5 then either j = 1 5 s j 11 or j = 1 6 s j 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 7 because the cases

( s 1 , s 2 , s 3 , s 4 , s 5 ) = ( 4 , 1 , 2 , 2 , 2 ) , ( 4 , 1 , 3 , 2 , 1 ) , ( 4 , 1 , 2 , 3 , 1 ) or ( 4 , 1 , 3 , 1 , 2 ) are not possible.

Thus implies that j = 1 5 s j 11 .

8.2) s 1 = 2 , s 2 = 3 , then j = 1 5 s j 10 and if j = 1 5 s j = 10 then

( s 1 , s 2 , s 3 , s 4 , s 5 ) = ( 2 , 3 , 1 , 3 , 1 ) . By Lemma 3.4, s 6 = 4 . Thus implies that j = 1 6 s j 14 .

8.3) s 1 = 3 , s 2 = 2 , then ( s 1 , s 2 , s 3 , s 4 , s 5 ) it has minimal numerals in the following cases ( s 1 , s 2 , s 3 , s 4 , s 5 ) = ( 3 , 2 , 2 , 2 , 2 ) , ( 3 , 2 , 1 , 4 , 1 ) or ( 3 , 2 , 3 , 1 , 3 ) and for the case

( s 3 , s 4 , s 5 ) = ( 1 , 3 , 1 ) is not compatible with the case ( s 1 , s 2 ) = ( 3 , 2 ) . Thus implies that

j = 1 5 s j 11 . This completes the proof. □

Theorem 3.5.

γ 2 ( P 5 × P n ) = { 2 n + n 7 : n 1 , 2 , 3 , 5 ( mod 7 ) , 2 n + n 7 + 1 : n 0 , 4 , 6 ( mod 7 ) .

Proof. By Result 3.3, we have γ 2 ( p 5 × p n ) = j = 1 n s j 15 n 7 . By Theorem 3.4, we get γ 2 ( p 5 × p n ) = 2 n + n 7 : n 1 , 2 , 3 , 5 ( mod 7 ) .

Now, for n 0 , 4 , 6 ( mod 7 ) , by Theorem 3.4, we have γ 2 ( p 5 × p n ) 2 n + n 7 + 1 . From Result 3.3, we have γ 2 ( p 5 × p n ) 2 n + n 7 . We will study the cases:

1) n 0 ( mod 7 ) . We have γ 2 ( p 5 × p n ) = 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,

γ 2 ( p 5 × p n ) = j = 1 n s j = s 1 + s 2 + s 3 + j = 4 n 4 s j + j = n 3 n s j 8 + 2 ( n 2 ) + n 7 7 + 9 , γ 2 ( p 5 × p n ) 17 + 2 n 14 + n 7 7 = 2 n + n + 14 7 = 2 n + n 7 + 2 2 n + n 7 + 1.

b) s 1 + s 2 5 if s 1 + s 2 6 then

γ 2 ( p 5 × p n ) = j = 1 n s j = s 1 + s 2 + j = 3 n 5 s j + j = n 4 n s j 6 + 2 ( n 7 ) + n 7 7 + 10 = 2 n + n 7 + 14 7 = 2 n + n 7 + 1.

Let s 1 + s 2 = 5 then by Lemma 3.8, j = 1 5 s j 11 or j = 1 6 s j 14 . If j = 1 5 s j 11 then

γ 2 ( p 5 × p n ) = j = 1 n s j = j = 1 5 s j + j = 6 n 2 s j + s n 1 + s n 11 + 2 ( n 7 ) + n 7 7 + 5 = 2 n + n 7 + 1 = 2 n + n 7 + 1.

{where the case s n 1 + s n = 4 is the same as s 1 + s 2 = 4 }. If j = 1 5 s j < 11 then by Lemma 3.8, we have j = 1 6 s j 14

γ 2 ( p 5 × p n ) = j = 1 n s j = s 1 + s 2 + j = 3 n 5 s j + j = n 4 n s j 6 + 2 ( n 7 ) + n 7 7 + 10 = 2 n + n 7 + 14 7 = 2 n + n 7 + 1.

And with Theorem 3.4, we get γ 2 ( p 5 × p n ) = 2 n + n 7 + 1 : n 0 ( mod 7 ) .

2) When n 4 ( mod 7 ) we have two cases:

a) s 1 + s 2 = 4 . Thus implies that s 1 + s 2 + s 3 = 8 then

γ 2 ( p 5 × p n ) = j = 1 n s j = j = 1 3 s j + j = 4 n 1 s j + s n 8 + 15 ( n 4 ) 7 + 2 = 2 n + n + 10 7 = 2 n + n 7 + 1.

b) s 1 + s 2 5 {where s n 1 + s n 5 } then

γ 2 ( p 5 × p n ) = j = 1 n s j = s 1 + s 2 + j = 3 n 2 s j + s n 1 + s n 5 + 2 ( n 4 ) + n 4 7 + 5 = 2 n + n + 10 7 = 2 n + n 7 + 1.

Then by Theorem 3.4, we get γ 2 ( p 5 × p n ) = 2 n + n 7 + 1 : n 4 ( mod 7 ) .

3) n 6 ( mod 7 ) . We have two cases:

a) If s 1 + s 2 = 4 then s 1 + s 2 + s 3 = 8 . Thus implies that

γ 2 ( p 5 × p n ) = j = 1 n s j = s 1 + s 2 + s 3 + j = 4 n 3 s j + s n 2 + s n 1 + s n 8 + 2 ( n 6 ) + n 6 7 + 6 = 2 n + n 7 + 1.

b) If s 1 + s 2 5 then s n 1 + s n 5 . Thus implies that

γ 2 ( p 5 × p n ) = j = 1 n s j = j = 1 4 s j + j = 5 n 2 s j + s n 1 + s n 9 + 2 ( n 6 ) + n 6 7 + 5 = 2 n + n + 8 7 = 2 n + n 7 + 1.

By Theorem 3.4, we get γ 2 ( p 5 × p n ) = 2 n + n 7 + 1 : n 6 ( mod 7 ) . Finally, we get

γ 2 ( p 5 × p n ) = { 2 n + n 7 : n 1 , 2 , 3 , 5 ( mod 7 ) , 2 n + n 7 + 1 : n 0 , 4 , 6 ( mod 7 ) .

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
[1]   Mohan, J.J. and Kelkar, I. (2012) Restrained 2-Domination Number of Complete Grid Graphs. International Journal of Applied Mathematics and Computation, 4, 352-358.

[2]   Fink, J.F. and Jacobson, M.S. (1985) n-Domination in graphs, in: Graph Theory with Application to Algorithms and Computer Science. John Wiley and Sons, New York, 282-300.

[3]   Fink, J.F. and Jacobson, M.S. (1985) On n-Domination, n-Dependence and Forbidden Subgraphs. In: Graph Theory with Application to Algorithms and Computer Science, John Wiley and Sons, New York, 301-311.

[4]   Haynes, T.W., Hedetniemi, S.T., Henning, M.A. and Slater, P.J. (2003) H-Forming Sets in Graphs. Discrete Mathematics, 262, 159-169.
https://doi.org/10.1016/S0012-365X(02)00496-X

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

[6]   Hansberg, A. and Volkmann, L. (2009) Upper Bounds on the k-Domination Number and the k-Roman Domination Number. Discrete Applied Mathematics, 157, 1634-1639.
https://doi.org/10.1016/j.dam.2008.10.011

[7]   Cockayne, E.J., Gamble, B. and Shepherd, B. (1985) An Upper Bound for the k-Domination Number of a Graph. Journal of Graph Theory, 9, 533-534.
https://doi.org/10.1002/jgt.3190090414

[8]   Blidia, M., Chellali, M. and Volkmann, L. (2006) Some Bounds on the p-Domination Number in Trees. Discrete Mathematics, 306, 2031-2037.
https://doi.org/10.1016/j.disc.2006.04.010

[9]   Favaron, O., Hansberg, A. and Volkmann, L. (2008) On k-Domination and Minimum Degree in Graphs. Journal of Graph Theory, 57, 33-40.
https://doi.org/10.1002/jgt.20279

[10]   Volkmann, L. (2010) A Bound on the k-Domination Number of a Graph. Czechoslovak Mathematical Journal, 60, 77-83.
https://doi.org/10.1007/s10587-010-0019-1

[11]   Shaheen, R. (2009) Bounds for the 2-Domination Number of Toroidal Grid Graphs. International Journal of Computer Mathematics, 86, 584-588.
https://doi.org/10.1080/00207160701690284

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

 
 
Top