OJDM  Vol.10 No.2 , April 2020
The Signed Domination Number of Cartesian Product of Two Paths
ABSTRACT
Let G be a finite connected simple graph with vertex set V(G) and edge set E(G). A function f:V(G) → {1,1} is a signed dominating function if for every vertex vV(G), the closed neighborhood of v contains more vertices with function values 1 than with −1. The signed domination number γs(G) of G is the minimum weight of a signed dominating function on G. In this paper, we calculate The signed domination numbers of the Cartesian product of two paths Pm and Pn for m = 3, 4, 5 and arbitrary n.

1. Introduction

Let G be a finite simple connected graph with vertex set V(G) and edge set E(G). The neighborhood of v, denoted N(v), is set { u : u v E ( G ) } and the closed neighborhood of v, denoted N[v], is set N ( v ) { v } . The function f is a signed dominating function if for every vertex v V , the closed neighborhood of v contains more vertices with function value 1 than with −1. The signed domination number of G, γ s ( G ) , is the minimum weight of a signed dominating function on G.

In [1], Dunbar et al. introduced this concept and it has been studied by several authors [1] [2] [3] [4], in [5] Haas and Wexler had found the signed domination number of P2 × Pn and P2 × Cn. In [6] Hosseini gave a lower and upper bound for the signed domination number for any graph.

We consider when we represent the Pm × Pn graph to find the signed dominating function that the black circles refer to the graph vertices which weight 1, and the white circles refer to the graph vertices which weight −1. Let f be a signed dominating function of the Pm × Pn graph and, A = { v V : f ( v ) = 1 } , B = { v V : f ( v ) = 1 } , then | A | + | B | = m n , is number of the graph vertices, and γ s ( P m × P n ) = m n 2 | B | = | A | | B | . Let Kj the jth column vertices, and also A i = { v K i : f ( v ) = 1 } , B i = { v K i : f ( v ) = 1 } then | A j | + | B j | = m .

2. Main Results

In this paper we will show three theorems to find the signed domination number of Cartesian product of Pm × Pn.

Theorem 2.1. Let n be a positive integer:

If n 0 ( mod 3 ) , then γ s ( P 3 × P n ) = 5 n 3 ;

If n 1 ( mod 3 ) , then γ s ( P 3 × P n ) = 5 ( n 1 ) 3 + 1 ;

If n 2 ( mod 3 ) , then γ s ( P 3 × P n ) = 5 ( n 2 ) 3 + 2 .

Proof: Case n ≡ 0 (mod 3)

Let f be a signed dominating function of (P3 × Pn), then for any j were 2 ≤ j ≤ n − 1, then k = i 1 j + 1 | B K | 2 . We discuss the following cases:

Case a. |Bj| = 2 (Figure 1)

We notices that the first and last columns can’t include more than one vertex of the B set vertices. But in the case 2 ≤ j ≤ n − 1 and |Bj| = 2, the vertices (1, j) and (3, j) belong to the B set vertices and all the K j + 1 th , K j 1 th vertices belong to the A set.

Case b. |Bj| = 1 (Figure 2)

We discuss the following cases:

b.1. If ( 1 , j ) B then all the vertices (1, j − 1), (2, j − 1), (1, j + 1) and (2, j + 1) belong to the A set, and one of the vertices (3, j − 1) or (3, j + 1) at most can belong to the B set vertices.

b.2. If ( 2 , j ) B then all the vertices (1, j − 1), (3, j − 1), (1, j + 1) and (3, j + 1) belong to the A set, and one vertex of the vertices (2, j − 1) or (2, j + 1) at most belong to the B set vertices.

b.3. If ( 3 , j ) B then all the vertices (2, j − 1), (3, j − 1), (2, j + 1) and (3, j + 1) belong to the A set, and one of the vertices (1, j − 1) or (1, j + 1) at most belong to the B set vertices.

Figure 1. Case a.

Figure 2. Case b.

Case c. |Bj| = 0 (Figure 3)

When the jth column doesn’t include any one of the B set vertices, it is possible that the vertices (1, j + 1) and (3, j + 1) belong to the B set provided that the j + 1th column isn’t the last column then all the j + 2th column vertices belong to the A set, or the tow vertices (1, j − 1) and (3, j − 1) belong to the B set provided that the j − 1th column isn’t the first one, and all the j − 2th column vertices belong to the A set.

Whereas the j + 1th column includes one of the B set vertices, then the j + 2th column will include one of the B set vertices at most. Also if the j − 1th column includes one of the B set then the j − 2 will include one of the B set vertices at most.

We conclude from the previous cases that if 2 ≤ j ≤ n – 1, then k = i 1 j + 1 | B K | 2 .

And all three successive columns include two vertices at most weighted with −1, so seven vertices at least is weighted the weight 1, consequently:

γ s ( P 3 × P n ) 5 n 3 : n 0 ( mod 3 )

To find the upper bound of the signed domination number of (P3 × Pn) graph, Let’s define B = { ( 0 , 3 j ) : 0 j n 1 3 ( 2 , 3 j + 1 ) : 0 j n 2 3 } (Figure 4).

If B is the previously defined set and represents the vertices have the weight −1, then every one of the P3 × Pn graph vertices achieves the signed dominating

function, and | B | 2 n 3 then: γ s ( P 3 × P n ) 3 n 2 ( 2 n 3 ) 5 n 3 .

Consequently: γ ( P 3 × P n ) = 5 n 3 : n 0 ( mod 3 ) .

Case n ≡ 1 (mod 3) (Figure 5)

If we add a column to the previous graph in case [ n 0 ( mod 3 ) ] then one vertex at most can have the weight −1, so, when we add that vertex to the B set this makes f a signed dominating function, so:

B = { ( 0 , 3 j ) : 0 j n 1 3 ( 2 , 3 j + 1 ) : 0 j n 2 3 } { ( n , 0 ) } .

Consequently: γ s ( P 3 × P n ) = 5 ( n 1 ) 3 + 1 .

Figure 3. Case c.

Figure 4. The B set.

Figure 5. Case n = 1 (mod 3).

Case n ≡ 2 (mod 3) (Figure 6)

In this case we add to two columns to the graph so, the numeral to the vertices in the B set at any two successive columns is less or equals 2, so the signed domination number will increase of 2 than the signed domination number in case of n 0 ( mod 3 ) . If we add the vertices (n, 2) and (n − 1, 0) to B set then f remains a signed dominating function of the graph, and

B = { ( 0 , 3 j ) : 0 j n 1 3 ( 2 , 3 j + 1 ) : 0 j n 2 3 } { ( 0 , n 1 ) , ( 2 , n ) } .

Consequently, the domination number will be:

γ s ( P 3 × P n ) = 5 ( n 2 ) 3 + 2 .

Theorem 2.2. Let n be a positive integer:

If n 1 ( mod 4 ) , then γ s ( P 4 × P n ) = 2 n ;

If n = 1 ( mod 4 ) , then γ s ( P 4 × P n ) = 2 n 2 .

Proof: Let f be a signed domination function of the (P4 × Pn) graph. And let A, B, Kj, Aj and Bj are the previously defined sets, Whatever j is then | B j | + | B j + 1 | 2 , we notice that Bj ≤ 2 so, discuss the following cases:

Case a. |Bj| = 2. Then:

a.1. K j B = { ( 1 , j ) , ( 4 , j ) } or K j B = { ( 2 , j ) , ( 3 , j ) } .

Figure 6. Case n = 2 (mod 3).

In this case all the j + 1th column vertices belong to the A set vertices so, the two remained vertices of the jth column (Figure 7):

a.2. K j B = { ( 1 , j ) , ( 3 , j ) } or K j B = { ( 2 , j ) , ( 4 , j ) } .

In this case one vertex at most j + 1th or j − 1th column vertices can belong to the B set vertices, either | B j | + | B j + 1 | 2 or | B j 1 | + | B j | 2 (Figure 8).

The vertices (1, j), (2, j) can’t belong to the B set at the same time, neither the vertices (3, j), (4, j) because both of the vertices (1, j), (4, j) from the third degree and can’t connect with any one of the B set vertices.

Case b. |Bj| = 1: then we discuss the following cases:

b.1. If ( 1 , j ) B or ( 4 , j ) B then one of the j + 1th column vertices at most can be from the B set vertices (Figure 9).

b.2. If ( 2 , j ) B or ( 3 , j ) B then two of the j + 1th column vertices at most can be from the B set, and in this case all the j + 2th column vertices are from the A set vertices, and one vertex of the j − 1th column vertices at most can belong to the B set vertices, in this case | B j + 1 | + | B j + 2 | 2 and also | B j 1 | + | B j | 2 (Figure 10).

In all previous cases we conclude that every two successive columns include two of the B set vertices at most, then γ s ( P 4 × P n ) 2 n . And the case of (b − 2) doesn’t achieve in case of [ n 0 ( mod 4 ) ] because if ( 2 , j ) B in the j − 1th column then ( 2 , j + 1 ) B , as if ( 3 , j ) B then ( 3 , j + 1 ) B . so, in case of n 0 ( mod 4 ) this will make γ s ( P 4 × P n ) 2 n .

To find the upper bound of the signed domination number of (P3 × Pn) graph, let’s define (Figure 11):

B = { ( 0 , 4 j ) , ( 3 , 4 j ) : 0 j n 1 4 ( 1 , 4 j + 2 ) , ( 2 , 4 j + 2 ) : 0 j n 3 4 } .

We noticed that if the B set vertices are the vertices which have the weight −1 of the P4 × Pn graph, every one of the graph vertices achieves the signed dominating function so, the signed domination number of the P4 × Pn graph will be: γ s ( P 4 × P n ) 4 n 2 n 2 n .

Consequently: γ s ( P 4 × P n ) = 2 n : n = 0 ( mod 4 ) .

Case n ≡ 1 (mod 4) (Figure 12)

If we add a column to the previous graph then the vertices (0, n) and (3, n) are of the B set vertices, so:

B = { ( 0 , 4 j ) , ( 3 , 4 j ) : 0 j n 1 4 ( 1 , 4 j + 2 ) , ( 2 , 4 j + 2 ) : 0 j n 3 4 } { ( 0 , n ) , ( 3 , n ) } .

Figure 7. Case a.1.

Figure 8. Case a.2.

Figure 9. Case b.1.

Figure 10. Case b.2.

Figure 11. The B set.

The signed domination number at the last column will be equal to zero, then number of the columns will increase of 1, without any increment for the signed domination number then γ s ( P 4 × P n ) = 2 ( n 1 ) = 2 n 2 .

Consequently: γ s ( P 4 × P n ) = 2 n 2 : n = 1 ( mod 4 ) .

Figure 12. Case n = 1 (mod 4).

Case n ≡ 2 (mod 4)

In this case we add to two columns of the graph, then we notice that the last column doesn’t include any one of the B set vertices so, the signed domination number then:

γ s ( P 4 × P n ) = 2 n : n 2 ( mod 4 ) .

Case n ≡ 3 (mod 4)

In this case when we add to three columns of the graph, then we notice that only one of the vertices (3, n) and (2, n) is from the B set. So, the signed domination number then:

γ s ( P 4 × P n ) = 2 n : n 3 ( mod 4 ) .

Consequently: γ s ( P 4 × P n ) = 2 n : n 1 ( mod 4 )

γ s ( P 4 × P n ) = 2 n 2 : n = 1 ( mod 4 ) .

Theorem 2.3. Let n be a positive integer, for n ≥ 5 then

If n = 0 ( mod 5 ) , then γ s ( P 5 × P n ) = 9 n 5 + 2 ;

If n = 2 , 4 ( mod 5 ) , then γ s ( P 5 × P n ) = 9 n 5 + 3 ;

If n = 1 , 3 ( mod 5 ) , then γ s ( P 5 × P n ) = 9 n 5 + 4 .

Proof: Let f be a signed domination function of the P5 × Pn graph. And A, B, Kj, Aj and Bj are the previously defined sets, then whatever 1 ≤ j ≤ n – 4, then:

i = j j + 4 | B i | 8 . We discuss the following cases:

Case a. |Bj| = 3 (Figure 13)

a.1. If (1, j), (3, j) and ( 5 , j ) B then ( 3 , j + 1 ) B and one of the vertices (2, j + 2) or (4, j + 2) is of the B set vertices and in the two cases (2, j + 3) and (4, j+ 3) are of the B set vertices and only one vertex of the j + 4th column.

a.2. If (1, j), (3, j) and ( 4 , j ) B then the j + 1th column doesn’t include any one of the B set vertices. The j + 2th column include three of the B set vertices, the j + 3th column doesn’t include any one of the B set vertices. Then every two successive columns include three vertices of the B set. And every ten successive columns include fifteen vertices of the B set.

Case b. |Bj| = 2:

b.1. If (1, j) and (3, j) Î B then (3, j + 1) and (5, j + 1) Î B, (2, j + 2) Î B and also (2, j + 3) and (4, j + 3) are of the B set vertices, And the j + 4th column include only the vertex (4, j + 4).

Figure 13. Case a.

b.2. If (1, j) and (4, j) Î B then (3, j + 1) Î B, (2, j + 2) and (5, j + 2) Î B, (2, j + 3) Î B, (3, j + 4) and (4, j + 4) Î B.

b.3. If (1, j) and (5, j) Î B then (3, j + 1) Î B. And the j + 2th column include one vertex of the B set vertices at most. And the j + 3th column include two vertices at most. And the j+4th column include only one vertex.

b.4. If (2, j) and (3, j) Î B then (4, j + 1) or (5, j + 1) Î B, and the j + 2th column include two vertices of the B set vertices at most, And the j + 3th column include one vertex at most. And the j + 4th column include only two vertices.

b.5. If (2, j) and (4, j) Î B then (2, j + 1), (4, j + 1) Î B. And the j + 2th column doesn’t include any one of the B set vertices (1, j + 3), (3, j + 3), (5, j + 3) Î B,

and (3, j + 4) Î B, Then if |Bj| = 2 then: i = j j + 4 | B j | 8 (Figure 14).

Case c. |Bj| = 1 (Figure 15)

c.1. If (1, j) Î B or (2, j) Î B or (4, j) Î B or (5, j) Î B then the j + 1th column include two of the B set vertices and the j + 2th column include one vertex at most. And the j + 3th column include two of the B set vertices at most. In this case the j + 4th column include one of the B set vertices at most.

c.2. If (3, j) Î B then (1, j+1)Î B, (3, j + 1) Î B, (5, j + 1) Î B. And the j + 2th column doesn’t include any one of the B set vertices. And the vertices (2, j + 3), (4, j + 3), (2, j + 4) and (4, j + 4) belong to the B set vertices and the other cases are repeated.

Whatever 1 ≤ j ≤ n – 4, then i = j j + 4 | B i | 8 .

All of the five successive columns include eight of the B set vertices, then:

γ s ( P 5 × P n ) 5 n 2 ( 8 n 5 ) γ s ( P 5 × P n ) 5 n 16 n 5 γ s ( P 5 × P n ) 9 n 5 .

Let’s defined:

B = { ( 1 , 5 j + 1 ) , ( 3 , 5 j + 1 ) : 0 j n 1 5 ( 3 , 5 j + 2 ) ( 5 , 5 j + 2 ) : 0 j n 2 5 } { ( 2 , 5 j + 3 ) : 0 j n 3 5 ( 2 , 5 j + 4 ) , ( 4 , 5 j + 4 ) : 0 j n 4 5 ( 4 , 5 j + 5 ) : 0 j n 5 5 }

then | B | = 8 n 5 (Figure 16).

Figure 14. Case b.

Figure 15. Case c.

Figure 16. The B set.

We noticed that if the B set vertices are the vertices which have the weight −1 of the graph P5 × Pn then every one of the graph vertices achieve the signed domination function then the signed domination number of the P5 × Pn graph will be:

γ s ( P 5 × P n ) 5 n 2 ( 8 n 5 ) then γ s ( P 5 × P n ) 9 n 5 .

But it proves easily, that the first and second columns of P5 × Pn, have at most three vertices of the B set vertices. As well the vertices (1, 1) and (3, 1) they cannot belong to set B in the same time, then if we delete the vertex (3, 1) of B set,

then the signed domination number of the P5 × Pn will be: γ s ( P 5 × P n ) = 9 n 5 + 2 .

Case n ≡ 0 (mod 5) (Figure 17)

If we add three columns at the beginning, two columns at the end and add the vertices (1, 1), (5, 1), (3, 2), (4, 3), (2, n − 1), (3, n − 1) and (5, n). So,

n 0 ( mod 5 ) , and γ s ( P 5 × P n ) = 9 n 5 + 2 .

Case n ≡ 2 (mod 5) (Figure 18)

Note that the last two columns contain three vertices of B set vertices, such the signed domination number in these two columns equals 4, then:

Figure 17. Case n = 0 (mod 5).

Figure 18. Case n = 2, 4 (mod 5).

Figure 19. Case n =1, 3 (mod 5).

γ s ( P 5 × P n ) = 9 ( n 2 ) 5 + 2 + 4 = 9 n 5 + 12 5 = 9 n 5 + 3 .

Case n ≡ 4 (mod 5)

Note that the last four columns contain six vertices of B set vertices, such the signed domination number in these columns equals 8, then:

γ s ( P 5 × P n ) = 9 ( n 4 ) 5 + 2 + 8 = 9 n 5 + 14 5 = 9 n 5 + 3 .

Consequently: γ s ( P 5 × P n ) = 9 n 5 + 3 : n = 2 , 4 ( mod 5 ) .

Case n ≡ 1, 3 (mod 5) (Figure 19)

In this case we note that when you delete one vertex of the B set vertices previously defined of the last column, and the signed domination number is increasing by 2 in both cases then:

γ s ( P 5 × P n ) = 9 n 5 + 4 .

Consequently: γ s ( P 5 × P n ) = 9 n 5 + 4 : n = 1 , 3 ( mod 5 ) .

3. Conclusion

In this paper, we studied The signed domination numbers of the Cartesian product of two paths Pm and Pn for m = 3, 4, 5 and arbitrary n. we will work to find the signed domination numbers of the Cartesian product of two paths Pm and Pn for arbitraries m and n.

Cite this paper
Hassan, M. , Al Hassan, M. and Mostafa, M. (2020) The Signed Domination Number of Cartesian Product of Two Paths. Open Journal of Discrete Mathematics, 10, 45-55. doi: 10.4236/ojdm.2020.102005.
References
[1]   Dunbar, J., Hedetniemi, S.T., Henning, M.A. and Slater, P.J. (1995) Signed Domination in Graphs. In: Graph Theory, Combinatorics and Applications, John Wiley & Sons, New York, 311-322.

[2]   Broere, I., Hattingh, J.H., Henning, M.A. and McRae, A.A. (1995) Majority Domination in Graphs. Discrete Mathematics, 138, 125-135.
https://doi.org/10.1016/0012-365X(94)00194-N

[3]   Cockayne, E.J. and Mynhardt, C.M. (1996) On a Generalization of Signed Dominating Functions of Graphs. Ars Combinatoria, 43, 235-245.

[4]   Favaron, O. (1996) Signed Domination in Regular Graphs. Discrete Mathematics, 158, 287-293.
https://doi.org/10.1016/0012-365X(96)00026-X

[5]   Haasa, R. and Wexlerb, T.B. (2004) Signed Domination Numbers of a Graph and Its Complement. Discrete Mathematics, 283, 87-92.
https://doi.org/10.1016/j.disc.2004.01.007

[6]   Hosseini, S.M. (2015) New Bounds on the Signed Domination Numbers of Graphs. Australasian Journal of Combinatorics, 61, 273-280.

 
 
Top