The Signed Domination Number of Cartesian Product of Two Paths

Mohammad Hassan, Muhsin Al Hassan, Mazen Mostafa

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

DOI: 10.4236/ojdm.2020.102005                

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 v∈V(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 P_m and P_n for m = 3, 4, 5 and arbitrary n.

Keywords

Path, Cartesian Product, Signed Dominating Function, Signed Domination Number

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 $\left\{u:uv\in E\left(G\right)\right\}$ and the closed neighborhood of v, denoted N[v], is set $N\left(v\right)\cup \left\{v\right\}$. The function f is a signed dominating function if for every vertex $v\in V$, the closed neighborhood of v contains more vertices with function value 1 than with −1. The signed domination number of G, ${\gamma }_s\left(G\right)$, 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 P₂ × P_n and P₂ × C_n. In [6] Hosseini gave a lower and upper bound for the signed domination number for any graph.

We consider when we represent the P_m × P_n 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 P_m × P_n graph and, $A=\left\{v\in V:f\left(v\right)=1\right\}$, $B=\left\{v\in V:f\left(v\right)=-1\right\}$, then $\left|A\right|+\left|B\right|=m\cdot n$, is number of the graph vertices, and ${\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 the j^th column vertices, and also $A_i=\left\{v\in K_i:f\left(v\right)=1\right\}$, $B_i=\left\{v\in K_i:f\left(v\right)=-1\right\}$ then $\left|A_j\right|+\left|B_j\right|=m$.

2. Main Results

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

Theorem 2.1. Let n be a positive integer:

If $n\equiv 0\left(\mathrm{mod}3\right)$, then ${\gamma }_s\left(P_3\times P_n\right)=\frac{5n}{3}$ ;

If $n\equiv 1\left(\mathrm{mod}3\right)$, then ${\gamma }_s\left(P_3\times P_n\right)=\frac{5\left(n-1\right)}{3}+1$ ;

If $n\equiv 2\left(\mathrm{mod}3\right)$, then ${\gamma }_s\left(P_3\times P_n\right)=\frac{5\left(n-2\right)}{3}+2$.

Proof: Case n ≡ 0 (mod 3)

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

Case a. |B_j| = 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 |B_j| = 2, the vertices (1, j) and (3, j) belong to the B set vertices and all the $K_{j+1^{\text{th}}}$, $K_{j-1^{\text{th}}}$ vertices belong to the A set.

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

We discuss the following cases:

b.1. If $\left(1,j\right)\in 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 $\left(2,j\right)\in 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 $\left(3,j\right)\in 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. |B_j| = 0 (Figure 3)

When the j^th 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 + 1^th column isn’t the last column then all the j + 2^th 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 − 1^th column isn’t the first one, and all the j − 2^th column vertices belong to the A set.

Whereas the j + 1^th column includes one of the B set vertices, then the j + 2^th column will include one of the B set vertices at most. Also if the j − 1^th 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 ${\displaystyle {\sum }_{k=i-1}^{j+1}\left|B_K\right|}\le 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:

${\gamma }_s\left(P_3\times P_n\right)\ge \frac{5n}{3}:n\equiv 0\left(\mathrm{mod}3\right)$

To find the upper bound of the signed domination number of (P₃ × P_n) graph, Let’s define $B=\left\{\left(0,3j\right):0\le j\le \lfloor \frac{n-1}{3}\rfloor \cup \left(2,3j+1\right):0\le j\le \lfloor \frac{n-2}{3}\rfloor \right\}$ (Figure 4).

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

function, and $\left|B\right|\ge \frac{2n}{3}$ then: ${\gamma }_s\left(P_3\times P_n\right)\le 3n-2\left(\frac{2n}{3}\right)\le \frac{5n}{3}$.

Consequently: $\gamma \left(P_3\times P_n\right)=\frac{5n}{3}:n\equiv 0\left(\mathrm{mod}3\right)$.

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

If we add a column to the previous graph in case $\left[n\equiv 0\left(\mathrm{mod}3\right)\right]$ 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=\left\{\left(0,3j\right):0\le j\le \lfloor \frac{n-1}{3}\rfloor \cup \left(2,3j+1\right):0\le j\le \lfloor \frac{n-2}{3}\rfloor \right\}\cup \left\{\left(n,0\right)\right\}$.

Consequently: ${\gamma }_s\left(P_3\times P_n\right)=\frac{5\left(n-1\right)}{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\equiv 0\left(\mathrm{mod}3\right)$. 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=\left\{\left(0,3j\right):0\le j\le \lfloor \frac{n-1}{3}\rfloor \cup \left(2,3j+1\right):0\le j\le \lfloor \frac{n-2}{3}\rfloor \right\}\cup \left\{\left(0,n-1\right),\left(2,n\right)\right\}$.

Consequently, the domination number will be:

${\gamma }_s\left(P_3\times P_n\right)=\frac{5\left(n-2\right)}{3}+2$.

Theorem 2.2. Let n be a positive integer:

If $n\ne 1\left(\mathrm{mod}4\right)$, then ${\gamma }_s\left(P_4\times P_n\right)=2n$ ;

If $n=1\left(\mathrm{mod}4\right)$, then ${\gamma }_s\left(P_4\times P_n\right)=2n-2$.

Proof: Let f be a signed domination function of the (P₄ × P_n) graph. And let A, B, K_j, A_j and B_j are the previously defined sets, Whatever j is then $\left|B_j\right|+\left|B_{j+1}\right|\le 2$, we notice that B_j ≤ 2 so, discuss the following cases:

Case a. |B_j| = 2. Then:

a.1. $K_j\cap B=\left\{\left(1,j\right),\left(4,j\right)\right\}$ or $K_j\cap B=\left\{\left(2,j\right),\left(3,j\right)\right\}$.

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

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

a.2. $K_j\cap B=\left\{\left(1,j\right),\left(3,j\right)\right\}$ or $K_j\cap B=\left\{\left(2,j\right),\left(4,j\right)\right\}$.

In this case one vertex at most j + 1^th or j − 1^th column vertices can belong to the B set vertices, either $\left|B_j\right|+\left|B_{j+1}\right|\le 2$ or $\left|B_{j-1}\right|+\left|B_j\right|\le 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. |B_j| = 1: then we discuss the following cases:

b.1. If $\left(\text{1},j\right)\in B$ or $\left(\text{4},j\right)\in B$ then one of the j + 1^th column vertices at most can be from the B set vertices (Figure 9).

b.2. If $\left(\text{2},j\right)\in B$ or $\left(\text{3},j\right)\in B$ then two of the j + 1^th column vertices at most can be from the B set, and in this case all the j + 2^th column vertices are from the A set vertices, and one vertex of the j − 1^th column vertices at most can belong to the B set vertices, in this case $\left|B_{j+1}\right|+\left|B_{j+2}\right|\le 2$ and also $\left|B_{j-1}\right|+\left|B_j\right|\le 2$ (Figure 10).

In all previous cases we conclude that every two successive columns include two of the B set vertices at most, then ${\gamma }_s\left(P_4\times P_n\right)\ge 2n$. And the case of (b − 2) doesn’t achieve in case of $\left[n\equiv 0\left(\mathrm{mod}4\right)\right]$ because if $\left(\text{2},j\right)\in B$ in the j − 1^th column then $\left(2,j+1\right)\notin B$, as if $\left(\text{3},j\right)\in B$ then $\left(3,j+1\right)\notin B$. so, in case of $n\equiv 0\left(\mathrm{mod}4\right)$ this will make ${\gamma }_s\left(P_4\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 11):

$B=\left\{\left(0,4j\right),\left(3,4j\right):0\le j\le \lfloor \frac{n-1}{4}\rfloor \cup \left(1,4j+2\right),\left(2,4j+2\right):0\le j\le \lfloor \frac{n-3}{4}\rfloor \right\}$.

We noticed that if the B set vertices are the vertices which have the weight −1 of the P₄ × P_n graph, every one of the graph vertices achieves the signed dominating function so, the signed domination number of the P₄ × P_n graph will be: ${\gamma }_s\left(P_4\times P_n\right)\le 4n-2n\le 2n$.

Consequently: ${\gamma }_s\left(P_4\times P_n\right)=2n:n=0\left(\mathrm{mod}4\right)$.

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:

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

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 ${\gamma }_s\left(P_4\times P_n\right)=2\left(n-1\right)=2n-2$.

Consequently: ${\gamma }_s\left(P_4\times P_n\right)=2n-2:n=1\left(\mathrm{mod}4\right)$.

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:

${\gamma }_s\left(P_4\times P_n\right)=2n:n\equiv 2\left(\mathrm{mod}4\right)$.

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:

${\gamma }_s\left(P_4\times P_n\right)=2n:n\equiv 3\left(\mathrm{mod}4\right)$.

Consequently: ${\gamma }_s\left(P_4\times P_n\right)=2n:n\ne 1\left(\mathrm{mod}4\right)$

${\gamma }_s\left(P_4\times P_n\right)=2n-2:n=1\left(\mathrm{mod}4\right)$.

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

If $n=0\left(\mathrm{mod}5\right)$, then ${\gamma }_s\left(P_5\times P_n\right)=\frac{9n}{5}+2$ ;

If $n=2,4\left(\mathrm{mod}5\right)$, then ${\gamma }_s\left(P_5\times P_n\right)=\frac{9n}{5}+3$ ;

If $n=1,3\left(\mathrm{mod}5\right)$, then ${\gamma }_s\left(P_5\times P_n\right)=\frac{9n}{5}+4$.

Proof: Let f be a signed domination function of the P₅ × P_n graph. And A, B, K_j, A_j and B_j are the previously defined sets, then whatever 1 ≤ j ≤ n – 4, then:

${\displaystyle {\sum }_{i=j}^{j+4}\left|B_i\right|}\le 8$. We discuss the following cases:

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

a.1. If (1, j), (3, j) and $\left(5,j\right)\in B$ then $\left(\text{3},j+\text{1}\right)\in \text{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 + 4^th column.

a.2. If (1, j), (3, j) and $\left(4,j\right)\in B$ then the j + 1^th column doesn’t include any one of the B set vertices. The j + 2^th column include three of the B set vertices, the j + 3^th 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. |B_j| = 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 + 4^th 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 + 2^th column include one vertex of the B set vertices at most. And the j + 3^th column include two vertices at most. And the j+4^th 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 + 2^th column include two vertices of the B set vertices at most, And the j + 3^th column include one vertex at most. And the j + 4^th 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 + 2^th 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 |B_j| = 2 then: ${\displaystyle {\sum }_{i=j}^{j+4}\left|B_j\right|}\le 8$ (Figure 14).

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

c.1. If (1, j) Î B or (2, j) Î B or (4, j) Î B or (5, j) Î B then the j + 1^th column include two of the B set vertices and the j + 2^th column include one vertex at most. And the j + 3^th column include two of the B set vertices at most. In this case the j + 4^th 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 + 2^th 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 ${\displaystyle {\sum }_{i=j}^{j+4}\left|B_i\right|}\le 8$.

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

${\gamma }_s\left(P_5\times P_n\right)\ge 5n-2\left(\frac{8n}{5}\right)\Rightarrow {\gamma }_s\left(P_5\times P_n\right)\ge 5n-\frac{16n}{5}\Rightarrow {\gamma }_s\left(P_5\times P_n\right)\ge \frac{9n}{5}$.

Let’s defined:

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

then $\left|B\right|=\frac{8n}{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 P₅ × P_n then every one of the graph vertices achieve the signed domination function then the signed domination number of the P₅ × P_n graph will be:

${\gamma }_s\left(P_5\times P_n\right)\le 5n-2\left(\frac{8n}{5}\right)$ then ${\gamma }_s\left(P_5\times P_n\right)\le \frac{9n}{5}$.

But it proves easily, that the first and second columns of P₅ × P_n, 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 P₅ × P_n will be: ${\gamma }_s\left(P_5\times P_n\right)=\frac{9n}{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\equiv 0\left(\mathrm{mod}5\right)$, and ${\gamma }_s\left(P_5\times P_n\right)=\frac{9n}{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).

${\gamma }_s\left(P_5\times P_n\right)=\frac{9\left(n-2\right)}{5}+2+4=\frac{9n}{5}+\frac{12}{5}=\frac{9n}{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:

${\gamma }_s\left(P_5\times P_n\right)=\frac{9\left(n-4\right)}{5}+2+8=\frac{9n}{5}+\frac{14}{5}=\frac{9n}{5}+3$.

Consequently: ${\gamma }_s\left(P_5\times P_n\right)=\frac{9n}{5}+3:n=2,4\left(\mathrm{mod}5\right)$.

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:

${\gamma }_s\left(P_5\times P_n\right)=\frac{9n}{5}+4$.

Consequently: ${\gamma }_s\left(P_5\times P_n\right)=\frac{9n}{5}+4:n=1,3\left(\mathrm{mod}5\right)$.

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 = 3, 4, 5 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.

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