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
PDF
HTML XML
361
Downloads
1,284
Views
Citations

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

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*.

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 P_{2} × P_{n} and P_{2} × 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{\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 (P_{6} × P_{n}), then for any j were 2 ≤ j ≤ n − 3, then
${\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
${\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_{6} × 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 \\ \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 \lfloor \frac{n+2}{5}\rfloor \\ \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 \lfloor \frac{n+3}{5}\rfloor \\ \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 \lfloor \frac{n+4}{5}\rfloor \\ \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 \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_{6} × 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_{7} × P_{n}), 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}\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
${\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_{7} × P_{n}) and B the graph vertices set which having the weight −1, then |B_{1}| + |B_{2}| + |B_{3}| ≤ 6. Except for a case (2, 3), (3, 3), (6, 3) Î B. Then |B_{1}| + |B_{2}| + |B_{3}| ≤ 7. In this case |B_{4}| = 1.

Proof:

Case a. |B_{2}| = 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}| = 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_{2}| = 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_{7} × P_{n}. 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}\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
${\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
${\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_{7} × 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 \\ \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 \lfloor \frac{n-1}{5}\rfloor \\ \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 \lfloor \frac{n-2}{5}\rfloor \\ \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 \lfloor \frac{n-3}{5}\rfloor \\ \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 \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_{7} × 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.

[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 |

Journals Menu

Contact us

+1 323-425-8868 | |

customer@scirp.org | |

+86 18163351462(WhatsApp) | |

1655362766 | |

Paper Publishing WeChat |

Copyright © 2024 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.