The Signed Domination Number of Cartesian Product of Two Paths

Show more

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

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_{3} × P_{n}), then for any j were 2 ≤ j ≤ n − 1, then
${\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,\text{}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,\text{}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,\text{}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 ${\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_{3} × 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_{3} × 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_{4} × 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,\text{}j\right),\left(4,\text{}j\right)\right\}$ or ${K}_{j}\cap B=\left\{\left(2,\text{}j\right),\left(3,\text{}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_{3} × 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_{4} × P_{n} graph, every one of the graph vertices achieves the signed dominating function so, the signed domination number of the P_{4} × 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\}\\ \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\{\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_{5} × 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:

${\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:
${\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 ${\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)\\ \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}}\text{\hspace{0.17em}}\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 \\ \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}}\text{\hspace{0.17em}}\cup \left(2,5j+4\right),\left(4,5j+4\right):0\le j\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}}\text{\hspace{0.17em}}\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_{5} × P_{n} then every one of the graph vertices achieve the signed domination function then the signed domination number of the P_{5} × 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_{5} × 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_{5} × 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.

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.