On Signed Domination of Grid Graph

Mohammad Hassan, Muhsin Al Hassan, Mazen Mostafa

Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria.

DOI: 10.4236/ojdm.2020.104010                

Abstract

Let G(V, E) be a finite connected simple graph with vertex set V(G). A function is a signed dominating function f : V(G)→{−1,1} if for every vertex v ∈ V(G), the sum of closed neighborhood weights of v is greater or equal to 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 P_m and P_n for m = 6, 7 and arbitrary n.

Keywords

Grid Graph, Cartesian Product, Signed Dominating Function, Signed Domination Number

1. Introduction

Let G be a finite simple connected graph with vertex set V(G). The neighborhood of v, denoted N(v), is set {u: uv Î 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 weight of f is the sum of the values of f at every vertex of G. The signed domination number of G, γ_s(G), is the minimum weight of a signed dominating function on G.

In [1] [2] [3] [4], Dunbar et al. introduced this concept, in [5] Haas and Wexler had found the signed domination number of P₂ × P_n and P₂ × C_n. In [6] Hosseini gave a lower and upper bound for the signed domination number for any graph. In [7] Hassan, Al Hassan and Mostafa had found the signed domination number of P_m × P_n for m = 3, 4, 5 and arbitrary n.

We consider when we represent the P_m × P_n graph. The weight of the black circle is 1, and the white circles refer to the graph vertices which weight −1.

Let f be a signed dominating function of the P_m × P_n and $A=\left\{\nu \in V:f\left(\nu \right)=1\right\}$, $V=\left\{\nu \in V:f\left(\nu \right)=-1\right\}$, then ${\gamma }_s\left(P_m\times P_n\right)=m\cdot n-2\left|B\right|=\left|A\right|-\left|B\right|$. Let K_j be the j^th column vertices, and also $A_j=\left\{\nu \in K_j:f\left(\nu \right)=1\right\}$, $B_j=\left\{\nu \in K_j:f\left(\nu \right)=-1\right\}$.

2. Main Results

In this paper we will show tow theorem to find the signed domination number of Cartesian product of P_m × P_n.

Theorem 2.1. For n ≥ 1 then

${\gamma }_s\left(P_6\times P_n\right)=\{\begin{array}{l}2n;\text{If}n\equiv 1\left(\mathrm{mod}5\right),\\ 2n+2;\text{If}n\equiv 2\left(\mathrm{mod}5\right),\\ 2n+4;\text{If}n\equiv 0,3,4\left(\mathrm{mod}5\right).\end{array}$

Proof:

Let ƒ be a signed dominating function of (P₆ × P_n), then for any j were 2 ≤ j ≤ n − 3, then ${\displaystyle {\sum }_{k=j-1}^{j+2}\left|B_K\right|}\le 8$. We discuss the following cases:

Case a. |B_j| = 4:

we notice that the first and last columns can’t include four of the B set vertices, but in the case 2 ≤ j ≤ n − 3 and |B_j| = 4, then the vertices (1, j), (3, j), (4, j), (6, j) Î B, and all of the j − 1^th, j + 1^th column’s vertices don’t contain any one of the B set vertices, so the (1, j + 2), (6, j + 2) vertices, then the j + 2^th column includes three of the B set vertices at most (Figure 1).

Case b. |B_j| = 3:

We discuss the following cases:

b-1. If (1, j), (3, j), (4, j) Î B then both of the j − 1^th, j + 1^th columns include at most one of the B set vertices, then the j + 2^th column includes at most three of the B set vertices.

b-2. If (1, j), (3, j), (5, j) Î B then the j − 1^th and j + 1^th columns include at most two of the B set vertices, and the j + 1^th column includes three of the B set vertices.

b-3. If (1, j), (3, j), (6, j) Î B then both of the j − 1^th, j + 1^th columns include at most one of the B set vertices. And the j + 2^th column includes two of the B set vertices.

b-4. If (1, j), (4, j), (5, j) Î B then only one of the j − 1^th, j + 1^th columns include at most one of the B set vertices, so (1, j + 2) Î A, then the j + 2^th column includes at most three of the B set vertices.

Figure 1. Case a.

b-5. If (1, j), (4, j), (6, j) Î B then both of the j − 1^th, j + 1^th columns include at most one of the B set vertices. Also (1, j + 2), (4, j + 2) and (6, j + 2) Î A then only two of the j + 2^th vertices belong to B set.

b-6. If (2, j), (3, j), (6, j) Î B then only one of the j − 1^th, j + 1^th column’s vertices belong to the B set vertices, then the j + 2^th column include at most four of the B set vertices (Figure 2).

Case c. |B_j| = 2:

We discuss the following cases:

c-1. If (1, j), (3, j) Î B then all of the j − 1^th, j + 1^th, j + 2^th columns include at most two of the B set vertices (Figure 3).

c-2. If (1, j), (4, j) Î B and the j − 1^th column include two of the B set vertices then the j + 1^th column include at most one of the B set vertices, so the j + 2^th column include at most three vertices (Figure 4).

c-3. If (1, j), (5, j) Î B or (1, j), (6, j) Î B, then all of the j − 1^th, j + 1^th, j + 2^th columns include at most two of the B set vertices (Figure 5).

c-4. If (2, j), (3, j) Î B then if the j − 1^th column includes two of the B set vertices, then the j + 1^th column includes at most one of the B set vertices, so the j + 2^th column includes at most three vertices (Figure 6).

Figure 2. Case b.

Figure 3. Case c-1.

Figure 4. Case c-2.

c-5. If (2, j), (4, j) Î B then the j − 1^th column includes at most three of the B set vertices, it is (2, j − 1), (4, j − 1), (6, j − 1) Î B, so the j + 1^th column includes one of the B set vertices, also the j + 2^th column includes three of the B set vertices and both of the j − 2^th , j + 3^th columns don’t include any one of the B set vertices, so the j + 4^th column includes four of the B set vertices and the j − 3^th column includes three of the B set vertices. then the eight columns include sixteen of the B set vertices. In other cases stay ${\displaystyle {\sum }_{k=j-1}^{j+2}\left|B_K\right|}\le 8$ (Figure 7).

c-6. If (2, j), (5, j) Î B then all of the j − 1^th, j + 1^th, j + 2^th columns include at most two of the B set vertices (Figure 8).

Figure 5. Case c-3.

Figure 6. Case c-4.

Figure 7. Case c-5.

Figure 8. Case c-6.

c-7. If (3, j), (4, j) Î B then all of the j − 1^th, j + 1^th, j + 2^th columns include at most two of the B set vertices (Figure 9).

Case d. |B_j| = 1:

We discuss the following cases:

d-1. If (1, j) Î B or (3, j) Î B or (4, j) Î B or (6, j) Î B then the j − 1^th column includes at most three of the B set vertices also both of the j + 1^th, j + 2^th columns include at most two of the B set vertices (Figure 10).

d-2. If (2, j) Î B or (5, j) Î B then both of the j − 1^th, j + 1^th columns includes at most three of the B set vertices, and the j + 2^th column includes at most one of the B set vertices (Figure 11).

From the previous cases we conclude ${\gamma }_s\left(P_6\times P_n\right)\ge 2n$.

To find the upper bound of the signed domination number of (P₆ × P_n) graph, let’s define (Figure 12).

$\begin{array}{l}B=\{\left(1,1+5i\right),\left(6,1+5i\right):0\le i\le \lfloor \frac{n-1}{5}\rfloor \\ \cup \left(3,2+5i\right),\left(4,2+5i\right):0\le i\le \lfloor \frac{n+2}{5}\rfloor \\ \cup \left(2,3+5i\right),\left(5,3+5i\right):0\le i\le \lfloor \frac{n+3}{5}\rfloor \\ \cup \left(2,4+5i\right),\left(5,4+5i\right):0\le i\le \lfloor \frac{n+4}{5}\rfloor \\ \cup \left(3,5+5i\right),\left(4,5+5i\right):0\le i\le \lfloor \frac{n+5}{5}\rfloor \}\end{array}$

Figure 9. Case c-7.

Figure 10. Case d-1.

Figure 11. Case d-2.

Figure 12. B set.

Case n ≡ 1 (mod 5).

If B is the previously defined set and represents the vertices have the weight −1, then every one of the P₆ × P_n vertices achieves the signed dominating function, and |B| ≥ 2n, then: ${\gamma }_s\left(P_6\times P_n\right)\le 6n-2\left(2n\right)=2n$. Consequently: ${\gamma }_s\left(P_6\times P_n\right)=2n:n\equiv 1\left(\mathrm{mod}5\right)$ (Figure 13).

Case n ≡ 2 (mod 5).

In this case, we delete one of the two vertices (3, n) or (4, n) from the previously defined set B vertices, then the signed domination number will increase by 2 than the signed domination number in case of n ≡ 1 (mod 5), and ƒ remains a signed dominating function of the graph. Consequently: ${\gamma }_s\left(P_6\times P_n\right)=2n+2:n\equiv 2\left(\mathrm{mod}5\right)$ (Figure 14).

Case n ≡ 0, 3, 4 (mod 5).

In this case we delete the B set vertices in the last column, then the signed domination number will increase by 4 than signed domination number in case of n ≡ 1 (mod 5). And ƒ remains a signed dominating function of the graph.

Consequently: $\gamma \left(P_6\times P_n\right)=2n+4:n\equiv 0,3,4\left(\mathrm{mod}5\right)$ (Figure 15).

Lemma 2.1.

Let f be a signed domination function of (P₇ × P_n), and B the graph vertices set which having the weight −1, Then for any j were 1 ≤ j ≤ n − 1, then ${\displaystyle {\sum }_{k=j}^{j+1}\left|B_K\right|}\le 5$. Except the following cases:

(3, j), (5, j) Î B, (1, j), (3, j), (5, j) Î B, (2, j), (3, j), (5, j) Î B or (3, j), (5, j), (7, j) Î B. Then ${\displaystyle {\sum }_{k=j}^{j+1}\left|B_K\right|}\le 6$ and in this case |B_j+2| + |B_j+3| ≤ 5.

Proof:

For any j were 1 ≤ j ≤ n then |B_j| ≤ 4.

Case a. |B_j| = 4:

The j + 1^th column includes at most one of the B set vertices, except case (1, j), (3, j), (5, j), (7, j) Î B. then the j + 1^th column includes two of the B set vertices (Figure 16).

Case b. |B_j| = 3:

The j + 1^th column includes at most two vertices except in the following cases:

(1, j), (3, j), (5, j) Î B, (2, j), (4, j), (6, j) Î B, (3, j), (5, j), (7, j) Î B. Then |B_j+1| = 3 (Figure 17).

Case c. |B_j| = 2:

The j + 1^th column includes at most three vertices, except in case (3, j), (5, j) Î B, then the j + 1^th column includes four of the B set vertices (Figure 18).

Figure 13. Case n ≡ 1 (mod 5).

Figure 14. Case n ≡ 2 (mod 5).

Figure 15. Case a.

Figure 16. Case a.

Figure 17. Case b.

Figure 18. Case c.

In case |B_j| = 1 or |B_j| = 0 it’s proofed easily because |B_j+1| ≤ 4.

Lemma 2.2.

Let ƒ be a signed domination function of (P₇ × P_n) and B the graph vertices set which having the weight −1, then |B₁| + |B₂| + |B₃| ≤ 6. Except for a case (2, 3), (3, 3), (6, 3) Î B. Then |B₁| + |B₂| + |B₃| ≤ 7. In this case |B₄| = 1.

Proof:

Case a. |B₂| = 3:

If (1, 3), (3, 3), (5, 3) Î B or (2, 3), (4, 3), (6, 3) Î B then the second column include three vertices of the B set vertices, and the first column doesn’t include any one of the B set vertices (Figure 19).

Case b. |B₂| = 2:

If (1, 3), (3, 3), (7, 3) Î B or (1, 3), (4, 3), (5, 3) Î B or (1, 3), (4, 3), (6, 3) Î B, then the second column include two vertices of the B set vertices, and the first column doesn’t include any one of the B set vertices.

If (1, 3), (3, 3), (4, 3) Î B or (1, 3), (3, 3), (6, 3) Î B or (1, 3), (5, 3), (6, 3) Î B or (2, 3), (3, 3), (5, 3) Î B or (2, 3), (4, 3), (5, 3) Î B, then the second column include two vertices of the B set vertices, and the first column include one of the B set vertices.

If (2, 3), (3, 3), (6, 3) Î B, then the second column include two vertices of the B set vertices, and the first column include two vertices of the B set vertices. In this case the fourth column at most include one of the B set vertices (Figure 20).

Case b. |B₂| = 1:

If (1, 3), (4, 3), (7, 3) Î B, then the second column include one of the B set vertices, and the first column include one of the B set vertices (Figure 21).

Remark 2.1. |B_n−2| + |B_n−1| + |B_n| ≤ 6. Except for a case (2, n − 2), (3, n − 2), (6, n − 2) Î B. Then |B_n−2| + |B_n−1| + |B_n| ≤ 7. In this case |B_n−3| = 1, and prove as in the lemma (2.2.)

Theorem 2.2. Let n be a positive integer

If n ≡ 0, 2 (mod 5), then ${\gamma }_s\left(P_7\times P_n\right)=\frac{11n}{5}+6$ ;

If n ≡ 1, 3 (mod 5), then ${\gamma }_s\left(P_7\times P_n\right)=\frac{11n}{5}+7$ ;

Figure 19. Case b.

Figure 20. Case b.

Figure 21. Case c.

If n ≡ 4 (mod 5), then ${\gamma }_s\left(P_7\times P_n\right)=\frac{11n}{5}+8$.

Proof:

Case n ≡ 0 (mod 5).

Let ƒ be a signed domination function of the P₇ × P_n. And B the graph vertices set which having the weight −1. Then for any j were 1 ≤ j ≤ n − 3 then ${\displaystyle {\sum }_{k=j-1}^{j+3}\left|B_K\right|}\le 12$.

Case a. |B_j| = 4:

Then we discuss the following cases:

a-1. If (2, j), (3, j), (5, j), (6, j) Î B then both of the j − 1^th, j + 1^th columns don’t include any one of the B set vertices, so |B_j−1| + |B_j| + |B_j+1| ≤ 4. And according to lema1 then |B_j+2| + |B_j+3| ≤ 6.

a-2. If (1, j), (3, j), (4, j), (6, j) Î B or (1, j), (3, j), (4, j), (7, j)ÎB or (1, j), (3, j), (5, j), (6, j) Î B. Then one of the j − 1^th or j + 1^th column includes one of the B set vertices, as |B_j+2| + |B_j+3| ≤ 6.

a-3. If (1, j), (3, j), (5, j), (7, j) Î B then both of the j − 1^th, j + 1^th columns include two of the B set vertices, as |B_j+2| + |B_j+3| ≤ 6 (Figure 22).

Case b. |B_j| = 3:

We discuss the following cases:

Figure 22. Case a.

b-1. If (1, j), (4, j), (7, j) Î B then at most one of the j − 1^th columns vertices and also at most one of the j + 1^th vertices belongs to the B set vertices. Then the number of the vertices from the B set in the five successive columns remains less or equal to 12 (Figure 23).

b-2. If (1, j), (3, j), (4, j) Î B or (1, j), (4, j), (5, j) Î B or (1, j), (4, j), (6, j) Î B or (1, j), (5, j), (6, j) Î B or (2, j), (3, j), (5 , j) Î B or (2, j), (3, j), (6, j) Î B or (2, j), (4, j), (5, j) Î B. then at most two of the j − 1^th columns vertices and also at most one of the j + 1^th vertices belongs to the B set vertices. Then the number of the vertices from the B set in the five successive columns remains less or equal to 12 (Figure 24).

b-3. If (2, j), (4, j), (6, j) Î B then at most one of the two vertices (2, j − 1), (2, j + 1) and one of the two vertices (4, j − 1), (4, j + 1), And one of the two vertices (6, j − 1), (6, j + 1) may be of the B set vertices. Then the number of the vertices from the B set in the five successive columns remains less or equal to 12 (Figure 25).

b-4. If (1, j), (3, j), (5, j) Î B then the j − 1^th column includes at most three of the B set vertices. In case |B_j−1| = 3. Then (3, j − 1), (5, j − 1), (7, j − 1) Î B. so (6, j + 1), (6, j + 2) Î B. Thus it remains in the j + 2^th column three successive vertices include at most two of the B set vertices, so the j + 3^th column includes at most two of the B set vertices (Figure 26).

b-5. If (1, j), (3, j), (7, j) Î B then both of the j − 1^th, j + 1^th columns include at most two of the B set vertices.

b-5-1. If (3, j − 1), (5, j − 1) Î B then (4, j + 1), (5, j + 1)Î B and (2, j + 2), (6, j + 2) Î B then three of the j + 3^th column vertices belongs to the B set vertices.

b-5-2. If (4, j − 1), (5, j − 1) Î B then (3, j + 1), (5, j + 1) Î B, and (2, j + 2), (5, j + 2) Î B or (2, j + 2), (6, j + 2) Î B, then at most three of the j + 3^th column vertices belong to the B set vertices (Figure 27).

b-6. If (1, j), (3, j), (6, j) Î B then the j − 1^th column includes at most two of the B set vertices, in this case the j + 1^th column includes at most two of the B set vertices, and the j + 2^th column includes at most three vertices and the j + 3^th column includes at most two vertices of the B set vertices (Figure 28).

Case c. |B_j| = 2:

c-1. If (1, j), (4, j) Î B or (1, j), (7, j) Î B then both of the j − 1^th, j + 1^th columns include at most two of the B set vertices, then the j − 1^th, j^th, j + 1^th columns

Figure 23. Case b-1.

Figure 24. Case b-2.

Figure 25. Case b-3.

Figure 26. Case b-4.

Figure 27. Case b-5.

Figure 28. Case b-6.

include at most six of the B set vertices, as any two columns include at most six vertices (Figure 29).

c-2. If (1, j), (3, j) Î B then the j − 1^th column includes at most three vertices, because one of the two vertices (3, j − 1) Î B or (4, j − 1) Î B and either the two vertices (5, j − 1) and (6, j − 1) or (5, j − 1) and (7, j − 1) belong to the B set vertices.

c-2-1. If (3, j − 1) Î B the j + 1^th column includes at most three of the B set vertices, in this case the j + 2^th column includes at most one of the B set vertices, and the j + 3^th column includes at most three vertices. Or the j + 2^th column includes two of the B set vertices and the j + 3^th column includes at most three vertices.

c-2-2. If (4, j − 1) Î B then the j + 1^th column includes at most three of the B set vertices, in this case (3, j + 1), (5, j + 1), (6, j + 1) Î B and (2, j + 2) Î B, so (2, j + 3), (4, j + 3), (5, j + 3), (7, j + 3) Î B, then the j − 2^th column includes at most one of the B set vertices, then ${\displaystyle {\sum }_{k=j-2}^{j+2}\left|B_K\right|}\le 12$. Also the j + 4^th column doesn’t include any one of the B set vertices, so ${\displaystyle {\sum }_{k=j}^{j+4}\left|B_K\right|}\le 12$. And according to lemma 2-1 note |B_j+5| + |B_j+6| ≤ 6, so |B_j+7| ≤ 6. Then every ten successive columns include at most twenty four of the B set vertices (Figure 30).

c-3. If (1, j), (5, j) Î B then the j − 1^th column includes at most three of the B set vertices, so the j + 1^th and j + 2^th columns includes at most two of the B set vertices, and the j + 3^th column includes at most three vertices (Figure 31).

c-4. If (1, j), (6, j) Î B then the j − 1^th column includes at most three vertices, in this case the j + 1^th column includes at most two of the B set vertices, also the j + 2^th column includes three of the B set vertices, and the j + 3^th column includes at most two vertices (Figure 32).

c-5. If (2, j), (3, j) Î B then the j − 1^th column includes at most three of the B set vertices, then the j + 1^th column includes two of the B set vertices which are (5, j + 1), (6, j + 1), also (1, j + 2), (3, j + 2), (4, j + 2)Î B, and the j + 3^th column includes only one of the B set vertices (Figure 33).

c-6. If (2, j), (4, j) Î B then the j − 1^th column includes at most three of the B set vertices, so the j + 1^th column includes at most two of the B set vertices, in this case the j + 2^th column includes at most three of the B set vertices, and the j + 3^th column includes at most two vertices (Figure 34).

c-7. If (2, j), (5, j) Î B then the j − 1^th column includes at most three of the B set vertices, and the j + 1^th column includes two of the B set vertices, then the j + 2^th, j + 3^th columns include at most five of the B set vertices (Figure 35).

Figure 29. Case c-1.

Figure 30. Case c-2.

Figure 31. Case c-3.

Figure 32. Case c-4.

Figure 33. Case c-5.

c-8. If (2, j), (6, j) Î B then both of the j − 1^th, j + 1^th columns include at most three of the B set vertices, so the j + 2^th column includes at most one of the B set vertices, and the j + 3^th column includes at most three vertices (Figure 36).

Figure 34. Case c-6.

Figure 35. Case c-7.

Figure 36. Case c-8.

c-9. If (3, j), (4, j) Î B then the j − 1^th column includes at most three of the B set vertices, then the j + 1^th column includes at most three of the B set vertices, then the j + 2^th column includes only one of the B set vertices, and the j + 3^th column includes at most three vertices (Figure 37).

c-10. If (3, j), (5, j) Î B then the j − 1^th column includes at most four of the B set vertices, so the j + 1^th column includes at most two vertices, then the j + 2^th column includes at most three of the B set vertices, and the j + 3^th column includes at most one vertex (Figure 38).

Case d. |B_j| = 1:

In this case the j + 1^th, j + 2^th columns include at most five of the B set vertices, so if the j + 3^th, j + 4^th columns include six of the B set vertices, then the number of the vertices in the five columns is less or equal to 12 (Figure 39).

We note from all the previous cases $\left|B\right|\le \frac{12n}{5}$. Then ${\gamma }_s\left(P_7\times P_n\right)\ge$ $7n-2\left(\frac{12n}{5}\right)=\frac{11n}{5}$.

To find the upper bound of the signed domination number of (P₇ × P_n) graph, let’s define (Figure 40).

Figure 37. Case c-9.

Figure 38. Case c-10.

Figure 39. Case d.

Figure 40. Case B.

$\begin{array}{l}B=\{\left(4,5j\right),\left(6,5j\right):0\le j\le \lfloor \frac{n}{5}\rfloor \\ \cup \left(2,5j+1\right),\left(4,5j+1\right),\left(6,5j+1\right):0\le j\le \lfloor \frac{n-1}{5}\rfloor \\ \cup \left(2,5j+2\right),\left(5,5j+2\right),\left(7,5j+2\right):0\le j\le \lfloor \frac{n-2}{5}\rfloor \\ \cup \left(3,5j+3\right),\left(5,5j+3\right):0\le j\le \lfloor \frac{n-3}{5}\rfloor \\ \cup \left(1,5j+4\right),\left(3,5j+4\right),\left(6,5j+4\right):0\le j\le \lfloor \frac{n-4}{5}\rfloor \}\end{array}$

If B the graph vertices set which having the weight −1, then every one of the P₇ × P_n graph vertices achieves the signed domination function and $\left|B\right|\ge \lfloor \frac{12n}{5}\rfloor$.

According to lemma 2-2 we deleted the vertex (4, 1) from the previously defined set B vertices in all cases, then ${\gamma }_s\left(P_7\times P_n\right)\ge \lfloor \frac{11n}{5}\rfloor +2$.

Case n ≡ 0, 2 (mod 5).

According to lemma 2-2, then in case n ≡ 0 (mod 5), we delete the vertices (3, n), (6, n), so in case n ≡ 2 (mod 5), we delete the vertex (4, n). Then the signed domination number will increase by 4.

Consequently: ${\gamma }_s\left(P_7\times P_n\right)=\lfloor \frac{11n}{5}\rfloor +2+4=\lfloor \frac{11n}{5}\rfloor +6:n\equiv 0,2\left(\mathrm{mod}5\right)$ (Figure 41).

Case n ≡ 1, 3 (mod 5).

When we add one column on case n ≡ 0 (mod 5), note that the number of vertices will increase by 7, and the number of set B vertices will increase by 2, in this case

${\gamma }_s\left(P_7\times P_n\right)=\lfloor \frac{11\left(n-1\right)}{5}\rfloor +2+7=\lfloor \frac{11n}{5}\rfloor +7:n\equiv 1\left(\mathrm{mod}5\right)$.

When we add three columns on case n ≡ 0 (mod 5), note that the number of vertices will increase by 21, and the number of set B vertices will increase by 5, in this case

${\gamma }_s\left(P_7\times P_n\right)=\lfloor \frac{11\left(n-3\right)}{5}\rfloor +2+21-2\times 5=\lfloor \frac{11n}{5}\rfloor +7:n\equiv 3\left(\mathrm{mod}5\right)$.

Consequently: ${\gamma }_s\left(P_7\times P_n\right)\ge \lfloor \frac{11n}{5}\rfloor +7:n\equiv 1,3\left(\mathrm{mod}5\right)$. (Figure 42)

Case n ≡ 4 (mod 5).

When we add four column on case n ≡ 0 (mod 5), note that the number of vertices will increase by 28, and the number of set B vertices will increase by 9, in this case (Figure 43)

${\gamma }_s\left(P_7\times P_n\right)=\lfloor \frac{11\left(n-4\right)}{5}\rfloor +2+28-2\times 7=\lfloor \frac{11n}{5}\rfloor +8:n\equiv 4\left(\mathrm{mod}5\right)$.

Figure 41. Case n ≡ 0, 2 (mode 5).

Figure 42. Case n ≡ 1, 3 (mode 5).

Figure 43. Case n ≡ 4 (mode 5).

3. Conclusion

In this paper, we studied the signed domination numbers of the Cartesian product of two paths P_m and P_n for m = 6, 7 and arbitrary n. We will work to find the signed domination numbers of the Cartesian product of two paths P_m and P_n for arbitraries m and n, and special graphs.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Dunbar, J., Hedetniemi, S.T., Henning, M.A. and Slater, P.J. (1995) Signed Domination in Graph Theory. In: Combinatorics and Applications, Wiley, New York, 1, 311-322.
[2]	Broere, I., Hattingh, J.H., Henning, M.A. and McRae, 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. (1995) 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.
[7]	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. https://doi.org/10.4236/ojdm.2020.102005