On Signed Domination of Grid Graph

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 Pm and Pn for m = 6, 7 and arbitrary n.

Share and Cite:

Hassan, M. , Al Hassan, M. and Mostafa, M. (2020) On Signed Domination of Grid Graph. Open Journal of Discrete Mathematics, 10, 96-112. doi: 10.4236/ojdm.2020.104010.

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 P2 × Pn and P2 × Cn. 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 Pm × Pn for m = 3, 4, 5 and arbitrary n.

We consider when we represent the Pm × Pn 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 Pm × Pn 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}×{P}_{n}\right)=m\cdot n-2|B|=|A|-|B|$. Let Kj be the jth 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 Pm × Pn.

Theorem 2.1. For n ≥ 1 then

${\gamma }_{s}\left({P}_{6}×{P}_{n}\right)=\left\{\begin{array}{l}2n;\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{If}\text{\hspace{0.17em}}n\equiv 1\left(\mathrm{mod}5\right),\\ 2n+2;\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{If}\text{\hspace{0.17em}}n\equiv 2\left(\mathrm{mod}5\right),\\ 2n+4;\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{If}\text{\hspace{0.17em}}n\equiv 0,3,4\left(\mathrm{mod}5\right).\end{array}$

Proof:

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

Case a. |Bj| = 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 |Bj| = 4, then the vertices (1, j), (3, j), (4, j), (6, j) Î B, and all of the j − 1th, j + 1th 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 + 2th column includes three of the B set vertices at most (Figure 1).

Case b. |Bj| = 3:

We discuss the following cases:

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

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

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

b-4. If (1, j), (4, j), (5, j) Î B then only one of the j − 1th, j + 1th columns include at most one of the B set vertices, so (1, j + 2) Î A, then the j + 2th 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 − 1th, j + 1th 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 + 2th vertices belong to B set.

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

Case c. |Bj| = 2:

We discuss the following cases:

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

c-2. If (1, j), (4, j) Î B and the j − 1th column include two of the B set vertices then the j + 1th column include at most one of the B set vertices, so the j + 2th 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 − 1th, j + 1th, j + 2th columns include at most two of the B set vertices (Figure 5).

c-4. If (2, j), (3, j) Î B then if the j − 1th column includes two of the B set vertices, then the j + 1th column includes at most one of the B set vertices, so the j + 2th 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 − 1th 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 + 1th column includes one of the B set vertices, also the j + 2th column includes three of the B set vertices and both of the j − 2th , j + 3th columns don’t include any one of the B set vertices, so the j + 4th column includes four of the B set vertices and the j − 3th column includes three of the B set vertices. then the eight columns include sixteen of the B set vertices. In other cases stay ${\sum }_{k=j-1}^{j+2}|{B}_{K}|\le 8$ (Figure 7).

c-6. If (2, j), (5, j) Î B then all of the j − 1th, j + 1th, j + 2th 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 − 1th, j + 1th, j + 2th columns include at most two of the B set vertices (Figure 9).

Case d. |Bj| = 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 − 1th column includes at most three of the B set vertices also both of the j + 1th, j + 2th 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 − 1th, j + 1th columns includes at most three of the B set vertices, and the j + 2th column includes at most one of the B set vertices (Figure 11).

From the previous cases we conclude ${\gamma }_{s}\left({P}_{6}×{P}_{n}\right)\ge 2n$.

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

$\begin{array}{l}B=\left\{\left(1,1+5i\right),\left(6,1+5i\right):0\le i\le ⌊\frac{n-1}{5}⌋\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\cup \left(3,2+5i\right),\left(4,2+5i\right):0\le i\le ⌊\frac{n+2}{5}⌋\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\cup \left(2,3+5i\right),\left(5,3+5i\right):0\le i\le ⌊\frac{n+3}{5}⌋\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\cup \left(2,4+5i\right),\left(5,4+5i\right):0\le i\le ⌊\frac{n+4}{5}⌋\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\cup \left(3,5+5i\right),\left(4,5+5i\right):0\le i\le ⌊\frac{n+5}{5}⌋\right\}\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 P6 × Pn vertices achieves the signed dominating function, and |B| ≥ 2n, then: ${\gamma }_{s}\left({P}_{6}×{P}_{n}\right)\le 6n-2\left(2n\right)=2n$. Consequently: ${\gamma }_{s}\left({P}_{6}×{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}×{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}×{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 (P7 × Pn), and B the graph vertices set which having the weight −1, Then for any j were 1 ≤ j ≤ n − 1, then ${\sum }_{k=j}^{j+1}|{B}_{K}|\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 ${\sum }_{k=j}^{j+1}|{B}_{K}|\le 6$ and in this case |Bj+2| + |Bj+3| ≤ 5.

Proof:

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

Case a. |Bj| = 4:

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

Case b. |Bj| = 3:

The j + 1th 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 |Bj+1| = 3 (Figure 17).

Case c. |Bj| = 2:

The j + 1th column includes at most three vertices, except in case (3, j), (5, j) Î B, then the j + 1th 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 |Bj| = 1 or |Bj| = 0 it’s proofed easily because |Bj+1| ≤ 4.

Lemma 2.2.

Let ƒ be a signed domination function of (P7 × Pn) and B the graph vertices set which having the weight −1, then |B1| + |B2| + |B3| ≤ 6. Except for a case (2, 3), (3, 3), (6, 3) Î B. Then |B1| + |B2| + |B3| ≤ 7. In this case |B4| = 1.

Proof:

Case a. |B2| = 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. |B2| = 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. |B2| = 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. |Bn−2| + |Bn−1| + |Bn| ≤ 6. Except for a case (2, n − 2), (3, n − 2), (6, n − 2) Î B. Then |Bn−2| + |Bn−1| + |Bn| ≤ 7. In this case |Bn−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}×{P}_{n}\right)=\frac{11n}{5}+6$ ;

If n ≡ 1, 3 (mod 5), then ${\gamma }_{s}\left({P}_{7}×{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}×{P}_{n}\right)=\frac{11n}{5}+8$.

Proof:

Case n ≡ 0 (mod 5).

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

Case a. |Bj| = 4:

Then we discuss the following cases:

a-1. If (2, j), (3, j), (5, j), (6, j) Î B then both of the j − 1th, j + 1th columns don’t include any one of the B set vertices, so |Bj−1| + |Bj| + |Bj+1| ≤ 4. And according to lema1 then |Bj+2| + |Bj+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 − 1th or j + 1th column includes one of the B set vertices, as |Bj+2| + |Bj+3| ≤ 6.

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

Case b. |Bj| = 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 − 1th columns vertices and also at most one of the j + 1th 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 − 1th columns vertices and also at most one of the j + 1th 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 − 1th column includes at most three of the B set vertices. In case |Bj−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 + 2th column three successive vertices include at most two of the B set vertices, so the j + 3th 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 − 1th, j + 1th 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 + 3th 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 + 3th column vertices belong to the B set vertices (Figure 27).

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

Case c. |Bj| = 2:

c-1. If (1, j), (4, j) Î B or (1, j), (7, j) Î B then both of the j − 1th, j + 1th columns include at most two of the B set vertices, then the j − 1th, jth, j + 1th 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 − 1th 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 + 1th column includes at most three of the B set vertices, in this case the j + 2th column includes at most one of the B set vertices, and the j + 3th column includes at most three vertices. Or the j + 2th column includes two of the B set vertices and the j + 3th column includes at most three vertices.

c-2-2. If (4, j − 1) Î B then the j + 1th 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 − 2th column includes at most one of the B set vertices, then ${\sum }_{k=j-2}^{j+2}|{B}_{K}|\le 12$. Also the j + 4th column doesn’t include any one of the B set vertices, so ${\sum }_{k=j}^{j+4}|{B}_{K}|\le 12$. And according to lemma 2-1 note |Bj+5| + |Bj+6| ≤ 6, so |Bj+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 − 1th column includes at most three of the B set vertices, so the j + 1th and j + 2th columns includes at most two of the B set vertices, and the j + 3th column includes at most three vertices (Figure 31).

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

c-5. If (2, j), (3, j) Î B then the j − 1th column includes at most three of the B set vertices, then the j + 1th 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 + 3th column includes only one of the B set vertices (Figure 33).

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

c-7. If (2, j), (5, j) Î B then the j − 1th column includes at most three of the B set vertices, and the j + 1th column includes two of the B set vertices, then the j + 2th, j + 3th 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 − 1th, j + 1th columns include at most three of the B set vertices, so the j + 2th column includes at most one of the B set vertices, and the j + 3th 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 − 1th column includes at most three of the B set vertices, then the j + 1th column includes at most three of the B set vertices, then the j + 2th column includes only one of the B set vertices, and the j + 3th column includes at most three vertices (Figure 37).

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

Case d. |Bj| = 1:

In this case the j + 1th, j + 2th columns include at most five of the B set vertices, so if the j + 3th, j + 4th 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 $|B|\le \frac{12n}{5}$. Then ${\gamma }_{s}\left({P}_{7}×{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 (P7 × Pn) 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\{\left(4,5j\right),\left(6,5j\right):0\le j\le ⌊\frac{n}{5}⌋\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\cup \left(2,5j+1\right),\left(4,5j+1\right),\left(6,5j+1\right):0\le j\le ⌊\frac{n-1}{5}⌋\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\cup \left(2,5j+2\right),\left(5,5j+2\right),\left(7,5j+2\right):0\le j\le ⌊\frac{n-2}{5}⌋\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\cup \left(3,5j+3\right),\left(5,5j+3\right):0\le j\le ⌊\frac{n-3}{5}⌋\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\cup \left(1,5j+4\right),\left(3,5j+4\right),\left(6,5j+4\right):0\le j\le ⌊\frac{n-4}{5}⌋\right\}\end{array}$

If B the graph vertices set which having the weight −1, then every one of the P7 × Pn graph vertices achieves the signed domination function and $|B|\ge ⌊\frac{12n}{5}⌋$.

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}×{P}_{n}\right)\ge ⌊\frac{11n}{5}⌋+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}×{P}_{n}\right)=⌊\frac{11n}{5}⌋+2+4=⌊\frac{11n}{5}⌋+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}×{P}_{n}\right)=⌊\frac{11\left(n-1\right)}{5}⌋+2+7=⌊\frac{11n}{5}⌋+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}×{P}_{n}\right)=⌊\frac{11\left(n-3\right)}{5}⌋+2+21-2×5=⌊\frac{11n}{5}⌋+7:n\equiv 3\left(\mathrm{mod}5\right)$.

Consequently: ${\gamma }_{s}\left({P}_{7}×{P}_{n}\right)\ge ⌊\frac{11n}{5}⌋+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}×{P}_{n}\right)=⌊\frac{11\left(n-4\right)}{5}⌋+2+28-2×7=⌊\frac{11n}{5}⌋+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 Pm and Pn for m = 6, 7 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, and special graphs.

Conflicts of Interest

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

 [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