Signed Domination Number of Some Graphs

Abstract

Let $G=(V,E)$ be a simple graph. A function $f:V\longrightarrow \{-1,1\}$ 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 weight of a function f is $\omega (f)= \sum _{v \in V} f(v)$. The signed domination number of G, $\gamma _s(G)$, is the minimum weight of a signed dominating function on G. A signed dominating function of weight $\gamma _s(G)$ is called $\gamma _s(G)$-function. A $\gamma _s(G)$-function can also be represented by a set of ordered pairs $S_f=\{(v, f(v)) :v\in V\}$. A subset T of $S_f$ is called a forcing subset of $S_f$ if $S_f$ is the unique extension of T to a $\gamma _s(G)$-function. The forcing signed domination number of $S_f$ $f(S_f, \gamma _s) = {\rm min} \{|T|: T$ is a forcing subset of $S_f\}$ and the forcing signed domination number of G, $f(G,\gamma _s)$, is defined by $f(G,\gamma _s) = {\rm min} \{f(S_f,\gamma _s): S_f$ is a $\gamma _s(G)$-function$\}$. In this paper, we deal with the signed domination number of several classes of graph. Also the forcing signed domination number of some graphs are determined.

1 Introduction

Let G be a simple graph with vertex set V and edge set E. The graph G is a complete t-partite graph if there is a partition $V=V_1 \cup \ldots \cup V_t$ of the vertex set, such that two vertices $v_1$ and $v_2$ are adjacent if and only if $v_1$ and $v_2$ are in the different parts of the partition. If $|V_k|=n_k$ $(1\le k\le t)$, then G is denoted by $K_{n_1,\ldots ,n_t}$. Let $G_1$ and $G_2$ be two graphs with vertex sets $V_1$ and $V_2$ and edge sets $E_1$ and $E_2$, respectively. The Cartesian product $G=G_1 \square G_2$ has the vertex set $V_1\times V_2$, and two vertices $(u_1,u_2)$ and $(v_1,v_2)$ of G are adjacent if and only if either $u_1=v_1$ and $u_2v_2 \in E_2$ or $u_2=v_2$ and $u_1v_1 \in E_1$. The direct product of G and H, denoted by $G\times H$ whose vertex set is $V(G)\times V(H)$, and for which vertices (g, h) and $(g',h')$ are adjacent precisely if $gg' \in E(G)$ and $hh' \in E(H)$. We say that $G= (V,E)$ is a join graph if G is the complete union of two graphs $G_1 = (V_1,E_1)$ and $G_2 = (V_2,E_2)$. In other words, $V = V_1 \cup V_2$ and $E = E_1 \cup E_2 \cup \{uv \vert u \in V_1, v \in V_2\}$. If G is the join graph of $G_1$ and $G_2$, then we write $G = G_1 +G_2$.

For a vertex $v \in V$, the closed neighborhood N[v] of v is the set consisting of v and all of its neighbors. For a function $g:V\longrightarrow \{-1,1\}$ and a vertex $v \in V$ we define $g(N[v])= \sum _{u \in N[v]} g(u)$. A signed dominating function of G is a function $g : V \longrightarrow \{-1,1\}$ such that $g (N[v])>0$ for all $v \in V$. The weight of a function g is $\omega (g)= \sum _{v \in V} g(v)$. The signed domination number, $\gamma _s(G)$, is the minimum weight of all signed dominating functions on G. A signed dominating function of weight $\gamma _s(G)$ is called a $\gamma _s(G)$-function. This concept was defined in Dunbar et al. (1995) and has been studied by several authors (see for instance Dunbar et al. 1995; Favaron 1996; Füredi and Mubayi 1999; Haas and Wexler 2004; Volkman and Zelinka 2005; Zelinka 2006). We denote g(N[v]) by g[v]. Also for signed dominating function g, the set $\{v \in V: g(v)=-1 \}$ denoted by $V^-_g$.

A signed dominating function g of G can also be represented by $S_g =\{ (v,g(v)) \, |\, v \in V \}$. Let g be a $\gamma _s(G)-$function. A subset T of $S_g$ is called a forcing subset of $S_g$, if $S_g$ is the unique extension of T to a $\gamma _s(G)-$function. The forcing signed domination number of $S_g$, $f(S_g,\gamma _s)$, is defined by $f(S_g,\gamma _s) = {\rm min} \{ |T|\, | \, T$ is a forcing subset of $S_g\}$. The forcing signed domination number of G is defined by $f(G,\gamma _s) = {\rm min} \{f(S_g,\gamma _s) \,|\, S_g$ is a $\gamma _s(G)-$function $\}$. The forcing signed domination number was introduced by Sheikholeslami in Sheikholeslami (2007) in which $f(G,\gamma _s)$ determined for several classes of graphs.

In this paper, we compute the signed domination number of several classes of graph, including $P_n + K_1$, $P_2 \Box K_{1,n}$, $P_2 \Box K_n$, $K_n \times K_m$ and $K_{n,\ldots ,n}$. Also, the forcing signed domination numbers of some graphs are determined.

2 Main Results

We begin with the following lemma to obtain the forcing signed domination number of complete graph $K_n$.

Lemma 1

Füredi and Mubayi (1999) Let G be a complete graph of order n. Then

$$\begin{aligned} \gamma _s(G)= \left\{ \begin{array}{ll} 1 & \quad \text {if}\ n\ \text {is odd}; \\ 2 & \quad \text {if}\ n\ \text {is even}. \end{array} \right. \end{aligned}$$

Theorem 1

The forcing signed domination number of complete graph $K_n$ is $\lceil \frac{n}{2} \rceil -1$.

Proof

Let $V(K_n)=\{v_1,v_2, \ldots , v_n \}$ and f be a $\gamma _s-$function of $K_n$. We have $|V^-_f|=\lceil \frac{n}{2}\rceil -1$. Without loss of generality, suppose that $f(v_i)=-1$ for $i=1,2,\ldots ,\lceil \frac{n}{2} \rceil -1$ which implies that $T=V^-_f$ is a forcing set of S. Hence, $f(G,\gamma _S)\le \lceil \frac{n}{2} \rceil -1$. On the contrary, assume that $T'$ is a forcing subset and $|T'|<\lceil \frac{n}{2} \rceil -1$. Since all vertices are adjacent, there are at least $\lceil \frac{n}{2} \rceil +1$ distinct extensions of $T'$ to a $\gamma _S$-function. This is a contradiction. $\square$

In the following two theorems, we consider the join graph of $P_n$ and $K_1$ and we determine the signed domination number as well as the forcing signed domination number of $P_n+K_1$. Let $V(P_{n}+K_{1})\;=\;{v_{0},v_{1}, \ldots, v_{n}}$ where $deg(v_0)=n$. If $n=1,2$, then $P_n+K_1$ is isomorphic to $P_2,K_3$ and so $\gamma _s(P_n+K_1)=2,1$, respectively. Also it is not hard to see that $\gamma _s(P_3+K_1)=2$. For $n \ge 4$, we deduce the following theorem.

Theorem 2

For $n \ge 4$, $\gamma _S(P_n + K_1)=n+1-2 \lceil \frac{n}{3} \rceil$.

Proof

Define $g:V\longrightarrow \{-1,1\}$ where $g(v_i)=-1$ if and only if $i=3k+1$ and $0\le k \le \left\lfloor \frac{n-1}{3} \right\rfloor$. For any $1 \le i \le n$, $\left| N[v_i]\cap V^-_g \right| =1$ and $deg(v_i)\ge 2$, so g is a signed dominating function and $\omega (g)=n+1-2\lceil \frac{n}{3}\rceil$. Hence, $\gamma _S(P_n + K_1)\le n+1-2\lceil \frac{n}{3}\rceil$. On the other side, let h be a $\gamma _s$-function of $P_n+K_1$ where $h(v_0)=-1$. Since $2\le deg(v_i)\le 3$ for $1\le i\le n$, so $h(v_i)=1$. Hence, $\omega (h)=n-1$ and as a result of that $\omega (h)>n+1-2\lceil \frac{n}{3}\rceil$. This is a contradiction. Thus, $h(v_0)=1$. If $h(v_i)=h(v_j)=-1$, then $|i-j|\ge 3$. As a consequence $|V^-_h| \le \lceil \frac{n}{3}\rceil$. Therefore, $\omega (h) \ge n+1-2\lceil \frac{n}{3}\rceil$. This completes the proof. $\square$

Lemma 2

Sheikholeslami (2007) For a graph G, $f(G,\gamma _s)=0$ if and only if G has a unique $\gamma _s$-function. Moreover, $f(G,\gamma _s)=1$ if and only if G does not have a unique $\gamma _s$-function but some pair $(v,\pm 1)$ belongs to exactly one $\gamma _s$-function.

Theorem 3

For $n \ge 1$,

$$f(P_{n} + K_{1} ,\gamma _{S} ) = \left\{ {\begin{array}{*{20}l} 0 \hfill & {n \equiv 1\quad \left( {\bmod 3} \right);} \hfill \\ 1 \hfill & {{\text{otherwise}}.} \hfill \\ \end{array} } \right.$$

Proof

Let k be a positive integer. There are three cases:

Case 1::

Let $n=3k+1$ and consider the $\gamma _s$-function g which is defined in proof of Theorem 2. Let h be another $\gamma _s$-function of $P_n+K_1$ . We show that $h=g$. On the contrary, suppose that $g \ne h$. So for some $0\le i \le k-1$, $V^-_h \cap \{v_{3i},v_{3i+2}\} \ne \emptyset$. Hence, $h(v_{3i\pm 1})=h(v_{3i\pm 2})=1$ or $h(v_{3i})=h(v_{3i\pm 1})=1$. So $|V^-_h|\le k$. Thus, $\omega (h) > \gamma _s(P_n+K_1)$. This is a contradiction. Thus, $g=h$ and by Lemma 2, $f(P_n+K_1,\gamma _s)=0$.

Case 2::

Let $n=3k$ and let h be a $\gamma _s$-function of $P_n+K_1$ such that $V^-_h=\{v_3, v_6, \ldots , v_n\}$. Then, in each induced subgraph of $\{v_1,v_2, \ldots , v_n\}$ which is isomorphic to $P_3$, there is exactly one vertex with label $-1$. Let $T=\{(v_3,-1)\}$. Then, T is a forcing subset of h and $f(P_n+K_1, \gamma _s)\le 1$. Since there are more than one $\gamma _s$-function for $P_n+K_1$, $f(P_n+K_1, \gamma _s)\ge 1$ and so $f(P_n+K_1,\gamma _s)=1$.

Case 3::

Let $n=3k+2$ and let g, h be two $\gamma _s$-functions of $P_n+K_1$ such that $V^-_g=\{v_2,v_5, \ldots , v_n\}$ and $V^-_h=\{v_1,v_4 , \ldots , v_{n-1}\}$. By Lemma 2, $f(P_n+K_1, \gamma _s)\ge 1$. Let $T=\{(v_2,-1)\}$ be a subset of g. Since $|V^-_g|=\lceil \frac{n}{3}\rceil$, so T is a forcing subset. Thus, $f(P_n+K_1,\gamma _s)\le 1$. This completes the proof.

$\square$

Now we consider the Cartesian product of $P_2$ and $K_{1,n}$. Let $V=\{ u_0,\dots , u_n, v_0, v_1, \dots , v_n \}$ be the vertex set of $P_2\square K_{1,n}$ where the induced subgraph on $\{ u_0,u_1, \dots , u_n\}$ and $\{ v_0, v_1, \dots , v_n \}$ are $K_{1,n}$. In Theorems 4 and 7, we determine signed domination and forcing signed domination numbers of $P_2\square K_{1,n}$.

Theorem 4

For $n\ge 1$, $\gamma _S(P_2 \square K_{1,n})=2$.

Proof

Let $g:V\longrightarrow \{-1,1\}$ such that $g(v)=-1$ if and only if $v \in \{v_1, \ldots v_{\lceil \frac{n}{2}\rceil }, u_{\lceil \frac{n}{2}\rceil +1}, \ldots , u_n\}$. Since $1 \le g[u_i],g[v_i]\le 3$ for $0\le i\le n$, g is a signed dominating function. Hence, $\gamma _s(P_2\square K_{1,n})\le \omega (g)=2$. Let h be a $\gamma _s$-function and $\omega (h)<2$. Then, $|V^-_h|>n$. So $h[u_0]=0$ or $h[v_0]=0$. This is a contradiction. Therefore, $\gamma _s(P_2\square K_{1,n})=2$. $\square$

Theorem 5

Zelinka (2006) Let $K_{a,b}$ be a complete bipartite graph with $b \le a$. Then

$$\gamma _{s} (K_{{a,b}} ) = \left\{ {\begin{array}{*{20}l} {a + 1} \hfill & {{\text{if }}\;b = 1;} \hfill \\ b \hfill & {{\text{if}}\;{\text{ }}2 \le b \le 3{\text{ }}\;{\text{and}}\;{\text{ }}a\;{\text{ is}}\;{\text{ even}};} \hfill \\ {b + 1} \hfill & {{\text{if }}\;2 \le b \le 3{\text{ }}\;{\text{and}}\;{\text{ }}a\;{\text{ is }}\;{\text{odd}};} \hfill \\ 4 \hfill & {{\text{if }}\;b \ge 4{\text{ }}\;{\text{and}}\;{\text{ }}a,b{\text{ }}\;{\text{are}}\;{\text{ both}}\;{\text{ even}};} \hfill \\ 6 \hfill & {{\text{if }}\;b \ge 4{\text{ }}\;{\text{and}}\;{\text{ }}a,b\;{\text{ are}}\;{\text{ both }}\;{\text{odd}};} \hfill \\ 5 \hfill & {{\text{if }}\;b \ge 4{\text{ }}\;{\text{and}}\;{\text{ }}a,b\;{\text{ have }}\;{\text{different}}\;{\text{ parity}}.} \hfill \\ \end{array} } \right.$$

Theorems 4 and 5 imply the following Corollary.

Corollary 1

For every positive integer n, $\gamma _s(P_2 \square K_{1,n})< \gamma _s(P_2)\times \gamma _s(K_{1,n})$.

Theorem 6

Sheikholeslami (2007) For $n \in \{3,4,5\}$, $f(C_n, \gamma _s)=1$ and for $n \ge 6$,

$$f(C_{n} ,\gamma _{s} ) = \left\{ {\begin{array}{*{20}l} 1 \hfill & {{\text{if }}n \equiv 0\quad \left( {\bmod 3} \right);} \hfill \\ 2 \hfill & {{\text{if }}n \equiv 1,2\quad \left( {\bmod 3} \right).} \hfill \\ \end{array} } \right.$$

Theorem 7

For $n\ge 1$, $f(P_2 \square K_{1,n},\gamma _s)=\lceil \frac{n}{2}\rceil$.

Proof

Let f be a $\gamma _s$-function of $P_2 \square K_{1,n}$. Then, $|V^-_f|=n$. If $n=1$, then $P_2 \square K_{1,n}\simeq C_4$ and by Theorem 6, $f(P_2 \square K_{1,n}, \gamma _s)=1$. Let $n \ge 2$. Since $|V^-_f|=n$ and $deg(v_i)=deg(u_i)=2$ for $1 \le i \le n$, so $u_0,v_0 \not \in V^-_f$. On the other hand, $|N(x) \cap V^-_f|\le \lceil \frac{n}{2}\rceil$ where $x \in \{u_0,v_0\}$. It is clear that $f(v_i)=-f(u_i)$ for $1\le i\le n$. Hence, $(v_i,f(v_i))$ forces $(u_i, f(u_i))$. Let $T\subseteq S_f$ where $|T|<\lceil \frac{n}{2}\rceil$. Then, there are at least two distinct extensions of T. Thus, T is not a forcing subset of f and so the forcing signed domination number of $P_2\times K_{1,n}$ is $\lceil \frac{n}{2}\rceil$. $\square$

Theorem 8

Sheikholeslami (2007) Let G be a graph with $\Delta \le 3$, g be a signed dominating function of G and $u,v \in V(G)$. If $g(u)=g(v)=-1$, then $d(u,v) \ge 3$.

Let $V=V_1 \cup V_2$ be the vertices set of $P_2\square K_n$ such that $V_1=\{v_1, \dots , v_n\}$ and $V_2=\{ u_1, \dots , u_n\}$ where induced subgraph on $V_i$ is $K_n$ for $1 \le i \le 2$. Also $u_j,v_j$ are adjacent for $1 \le j \le n$. Now, we obtain the signed domination number of $P_2\square K_n$.

Theorem 9

For any positive integer n,

$$\begin{aligned} \gamma _s(P_2 \square K_n)= \left\{ \begin{array}{ll} 2 & \quad n=2;\\ 4 & \quad 2<n \, \text { is even or } n=3 ;\\ 6 & \quad 3<n \, \text { is odd}. \end{array}\right. \end{aligned}$$

Proof

If $n=2$, then $P_2 \square K_n \simeq C_4$ and so $\gamma _s(P_2 \square K_n)=2$. If $n=3$, then $P_2 \square K_n$ is a 3-regular graph of diameter two. Let f be a $\gamma _s$-function of $P_2 \square K_n$. By Theorem 8, $|V^-_f|=1$. Thus, $\gamma _s(P_2 \square K_n)=4$.

Consider two following cases when $n>3$.

Case 1::

Let n be even. Define $f: V(P_2 \square K_n) \longrightarrow \{-1 , 1\}$, where $f(v)=-1$ if and only if $v \in \{v_1, \ldots , v_{\frac{n}{2}-1}\}\cup \{u_{\frac{n}{2}}, \ldots , u_{n-2} \}$. For each $v \in V$, $1 \le f[v] \le 3$ and also $\omega (f)=4$. Thus, $\gamma _s(P_2 \square K_n ) \le 4$. Let g be a $\gamma _s$-function of $P_2 \square K_n$. If $n=4$, then $|V_i \cap V^-_g| \le 2$ for $1 \le i \le 2$. Also if $|V_1 \cap V^-_g|=2$, then $V_2 \cap V^-_g=\emptyset$ and so $\omega (g)=4$. Hence, $\gamma _s(P_2 \square K_4)=4$. Let $n>4$. Since the Cartesian product of $P_2$ and $K_n$ is n-regular graph, so there are at most $\frac{n}{2}$ vertices of label $-1$ in the closed neighborhood of each vertex. Without loss of generality, let $|V_1 \cap V^-_g|=\frac{n}{2}$. Then, $V_2 \cap V^-_g =\emptyset$. Hence, $\omega (g)=n > 4$. This is contradiction by $\gamma _s(P_2 \square K_n)\le 4$. Thus, for $1 \le i \le 2$, $|V_i \cap V^-_g| \le \frac{n}{2} -1$ and so $\omega (g)=\gamma _s(P_2 \square K_n) \ge 4$.

Case 2::

Let n be odd. Define $f: V(P_2 \square K_n) \longrightarrow \{-1 , 1\}$, where $f(v)=-1$ if and only if $v \in \{v_1, \ldots , v_{\lfloor \frac{n}{2}\rfloor -1}\}\cup \{u_{\lfloor \frac{n}{2}\rfloor }, \ldots , u_{n-3} \}$. For each $v \in V$, $2 \le f[v] \le 4$ and also $\omega (f)=6$. Thus, $\gamma _s(P_2 \square K_n ) \le 6$. Let h be a $\gamma _s$-function of $P_2 \square K_n$. If $n=5$, then $|V_i \cap V^-_h| \le 2$ for $1 \le i \le 2$. Also if $|V_1 \cap V^-_h|=2$, then $V_2 \cap V^-_h=\emptyset$ and so $\gamma _s(P_2 \square K_4)=6$. Let $n>5$. Let $|V_1 \cap V^-_h|=\lfloor \frac{n}{2}\rfloor$. If for some $1 \le j \le n$, $h(u_j)=-1$, then $h[v_j]=0$ which is a contradiction. Hence, $V_2 \cap V^-_h=\emptyset$ and so $\omega (h)=n+1 >6$. This is not true. Thus, for $1 \le i \le 2$, $|V_i \cap V^-_h| \le \lfloor \frac{n}{2} \rfloor -1$ and so $\gamma _s(P_2 \square K_n) \ge 6$. This completes the proof.

$\square$

By Theorems 1 and 9, we have following Corollary.

Corollary 2

For $n>2$, $\gamma _S(P_2 \square K_n)\ge \gamma _s(P_2)\times \gamma _s(K_n)$.

Theorem 10

Let G be a complete n-partite graph with $n^2$ vertices where $n \ge 3$. Then

$$\begin{aligned} \gamma _s(G )= \left\{ \begin{array}{ll} 3 & \quad \text {if n is odd};\\ 4 & \quad \text {if n is even}. \end{array} \right. \end{aligned}$$

Proof

Let G be a complete n-partite graph. Let $V=A_1\cup \ldots \cup A_n$ where $A_i=\{ v_{ij}:\, 1\le j \le n\}$ and induced subgraph on $A_i$ has no edge for $1 \le i \le n$. Let n be odd. We define $f:V\rightarrow \{-1,1 \}$ such that $f(v)=-1$ if and only if $v \in \left\{ v_{ij}: 1\le i \le \lfloor \frac{n}{2}\rfloor -1 \text { and } 1 \le j \le \lceil \frac{n}{2}\rceil \right\} \cup \left\{ v_{ij}: \lfloor \frac{n}{2}\rfloor \le i \le n \text { and } 1 \le j \le \lfloor \frac{n}{2}\rfloor \right\}$. It is not hard to see that for any $v \in V$, $|N[v] \cap V^-_f|=|V^-_f|- \lfloor \frac{n}{2}\rfloor +1$ and $f[v] \ge 1$ and so f is a signed dominating function of weight $\omega (f)=3$. As a consequence, $\gamma _S(G)\le 3$. On the contrary, suppose that there is a $\gamma _s$-function g such that $\omega (g) <3$. Hence, $|V^-_g|> \frac{1}{2}(n^2-3)$. Let $|V^-_g|=\frac{1}{2}(n^2-1)$. Two following steps help us to reach the result.

• If $A_i \cap V^-_g=\emptyset$ for some $1\le i \le n$, then $g[v]=2-n$ for any $v \in A_i$ and since $n \ge 3$, $g[v] < 0$. This is not true. Hence, $A _i \cap V^-_g \ne \emptyset$ for every $1 \le i \le n$.

• If $|A_i \cap V^-_g| \ge \lceil \frac{n}{2}\rceil$ for every $1 \le i \le n$, then $|V^-_g| \ge \frac{1}{2}(n^2+n)$. This is impossible. So there is $1 \le j \le n$ such that $|A_j \cap V^-_g| \le \lfloor \frac{n}{2}\rfloor$. Let $u \in A_j \cap V^-_g$. Then,

  $$\begin{aligned} g[u]&= n^2-n+1-2\left( \frac{1}{2} (n^2-1) -|A_j \cap V^-_g|+1 \right) \\ &\quad \le 2 \lfloor \frac{n}{2} \rfloor -n \le -1. \end{aligned}$$

This is a contradiction. Therefore, $\gamma _S(G)=3$ when n is odd.

Now suppose that n is even and we define $f:V \longrightarrow \{-1,1\}$ such that $f(v)=-1$ if and only if $v \in \{v_{ij}: 1 \le i \le n-2 \text { and } 1\le j \le \frac{n}{2} \} \cup \{ v_{ij}: n-1 \le i \le n \text { and } 1 \le j \le \frac{n}{2} -1\}$. It is easily seen that $1 \le f[v] \le 5$ for each $v \in V$. Hence, f is a signed dominating function and $\omega (f)=4$.

Let g be a $\gamma _s$-function where $|V^-_g|=|V^-_f|+1$. We show that for any $1 \le i \le n$, $A_i \cap V^-_g \ne \emptyset$. On the contrary, let $A_k\cap V^-_g =\emptyset$ for some $1 \le k \le n$ and $u \in A_k$. Then, $g[u]=3-n\le 0$. This is a contradiction. Thus, for any $1 \le i \le n$, $A_i \cap V^-_g \ne \emptyset$. Let $w \in A_i \cap V^-_g$. Then, $g[w]=n^2-n+1-2 \left| |V^-_g|-|A_i\cap V^-_g|+1 \right| \ge 1$. So $|A_i \cap V^-_g| \ge \frac{n}{2}$ for any $1 \le i \le n$ and so $\frac{n^2}{2}-1=|V^-_g|\ge n(\frac{n}{2})$ which is impossible. Therefore, $\gamma _s(G)=4$ where n is even. This completes the proof. $\square$

Theorem 11

Dunbar et al. (1995), Henning and Slater (1996) Let G be a $k-$regular graph of order n. If k is odd, then $\gamma _{_S}(G )\ge \frac{2n}{k+1}$ and if k is even, then $\gamma _{_S}(G)\ge \frac{n}{k+1}$.

Let $V=\{v_{ij}:1\le i \le n \, , \, 1 \le j \le m \}$ be the vertex set of $K_n \times K_m$ for any positive integers $1<n < m$. Then, $v_{ij}$ and $v_{ks}$ are adjacent if and only if $i \ne k$ and $j \ne s$. Also for any $1 \le i \le n$ and $1 \le j \le m$, the induced subgraphs on $A_i=\{v_{ij}: 1\le j \le m \}$ and $B_j =\{v_{ij}: 1 \le i \le n\}$ are empty. With these notations in mind, we will prove the following result:

Theorem 12

For any positive integers $1<n < m$,

$$\begin{aligned} \gamma _s(K_n \times K_m)= \left\{ \begin{array}{ll} 2 & \quad n=2, m \text { is odd}; \\ 4 & \quad n=2, m \text { is even};\\ 3 & \quad n=3, m \text { is odd};\\ 5 & \quad n\ne 3, mn\text { is odd} ;\\ 6 & \quad 3< n <m \text { have different parity};\\ 8 & \quad 2 \ne n , m \text { are both even}. \end{array} \right. \end{aligned}$$

Proof

Consider following cases:

Case 1.:

If $n=2$, then $K_n \times K_m$ is a bipartite graph and $(m-1)$-regular. Define $f:V \longrightarrow \{-1,1\}$ such that $f(v_{ij})=-1$ if and only if $1 \le i \le 2$ and $1 \le j \le \lceil \frac{m}{2}\rceil -1$. Since for any i and j, $\left| N[v_{ij}] \cap V^-_f \right| \le \lceil \frac{m}{2}\rceil -1$, so $f[v_{ij}] \ge 1$. Thus, f is a signed dominating function and $\omega (f)=2,4$ and so $\gamma _s(K_n \times K_m) \le 2,4$ depending on m is odd or even, respectively. On the other hand, by Theorem 11, if m is odd, then $\gamma _s(K_n \times K_m) \ge 2$, otherwise $\gamma _s(K_n \times K_m) \ge 4$.

Case 2.:

If $n=3$ and m is odd. Define $f:V\longrightarrow \{-1,1\}$ such that $f(v_{ij})=-1$ if and only if $1 \le i \le 3$ and $1 \le j \le \lfloor \frac{m}{2}\rfloor$. Hence, $|N[v_{ij}] \cap V^-_f| \le 2\lfloor \frac{m}{2}\rfloor$ for any i and j. So f is a signed dominating function of weight $\omega (f)=3$.

If g is a $\gamma _s$-function and $\gamma _s(K_3 \times K_m) < \omega (f)$, then $|V^-_g| > |V^-_f|$. Let $|V^-_g|=|V^-_f|+1=\frac{3m-1}{2}$. Let $1 \le i \le 3$ and $A_i \cap V^-_g = \emptyset$. Then, $g[u]=3-m$ for each $u \in A_i$. So for any $1 \le i \le 3$, $A_i \cap V^-_g \ne \emptyset$. The same argument shows $B_j \cap V^-_g \ne \emptyset$ for any $1 \le j \le m$. If there is $1 \le \ell \le m$ such that $|B_{\ell }\cap V^-_g|=2$, then for $v_{i\ell } \in V^-_g$ we have

$$\begin{aligned} g[v_{i\ell }]= & 2m-1\\&-2 \left( |V^-_g|-|A_i\cap V^-_g|-|B_{\ell }\cap V^-_g|+2 \right) \ge 1 \end{aligned}$$

As a consequence $|A_i \cap V^-_g|\ge \frac{m+1}{2}$. Since $|V^-_g|= \sum _{i=1}^{3} |A_i \cap V^-_g|$, so $|V^-_g| \ge \frac{3m+3}{2}$. This is not true. Thus, for any $1 \le j \le m$, $|B_j \cap V^-_g|=1$ and so $|V^-_g|=m$. Again this is not true. Therefore, $\gamma _s(K_3\times K_m)=3$.

Case 3.:

Let $n \ne 3$ and mn is odd. Define $f:V\longrightarrow \{-1,1\}$ such that $f(v)=-1$ if and only if $v \in \left\{ v_{ij}: \, i\equiv 1+k \pmod n \, , \, j \equiv 1+k \pmod m \, , \, 1 \le k \le \frac{mn-5}{2} \right\}$. Thus, for any i, j, $\lfloor \frac{m}{2}\rfloor \le |A_i \cap V^-_f| \le \lceil \frac{m}{2}\rceil$ and $\lfloor \frac{n}{2}\rfloor \le |B_j\cap V^-_f| \le \lceil \frac{n}{2}\rceil$. Hence, for $v \in V$, $|N[v] \cap V^-_f| \le \frac{mn-1}{2}- \lfloor \frac{m}{2}\rfloor - \lfloor \frac{n}{2}\rfloor$ and so $f[v] \ge 1$. So f is a signed dominating function of weight $\omega (f)=5$. Hence, $\gamma _s(K_n \times K_m) \le 5$.

Let g be a signed dominating function where $\omega (g) <5$. Then, $|V^-_g| > \frac{mn-5}{2}$. Let $|V^-_g|=\frac{mn-3}{2}$. Suppose that $A_i \cap V^-_g=\emptyset$. If there is $B_j$ for some $1 \le j \le m$ such that $|B_j \cap V^-_g| \le \lfloor \frac{n}{2}\rfloor$, then

$$\begin{aligned} g[v_{ij}] = (m-1)(n-1)+1-2 \left( |V^-_g|-|B_j \cap V^-_g| \right) \le 4-n <0. \end{aligned}$$

Hence, for any $1 \le j \le m$, $|B_j \cap V^-_g| \ge \lceil \frac{n}{2} \rceil$ and then $|V^-_g| \ge m \lceil \frac{n}{2} \rceil$. This makes a contradiction. Therefore, $A_i \cap V^-_g \ne \emptyset$ for any $1 \le i \le n$. By similar argument, we can see $B_j \cap V^-_g \ne \emptyset$ for $1 \le j \le m$. If there are i and j such that $|A_i \cap V^-_g| \le \lfloor \frac{m}{2}\rfloor$, $|B_j \cap V^-_g| \le \lfloor \frac{n}{2}\rfloor$ and also $v_{ij} \in V^-_g$, then

$$\begin{aligned} g[v_{ij}]= (m-1)(n-1)+1-2 \left( |V^-_g|-|A_i \cap V^-_g| - |B_j \cap V^-_g| +2 \right) . \end{aligned}$$

Thus $g[v_{ij}]\le -1$. This is a contradiction. Otherwise, i.e., for any i, j, where$|A_i \cap V^-_g| \le \lfloor \frac{m}{2}\rfloor$, $|B_j \cap V^-_g| \le \lfloor \frac{n}{2}\rfloor$, $g(v_{ij})=+1$, then $|V^-_g| \ge \lfloor \frac{m}{2}\rfloor \lceil \frac{n}{2}\rceil +\lfloor \frac{n}{2}\rfloor \lceil \frac{m}{2}\rceil$ which is not true. Therefore, for any $1 \le i \le n$, $|A_i \cap V^-_g| \ge \lceil \frac{m}{2}\rceil$ or $|B_j \cap V^-_g| \ge \lceil \frac{n}{2} \rceil$ for any $1 \le j \le m$. But both cases are impossible. Hence, $\gamma _s(K_n \times K_m)=5$.

Case 4.:

Let $n>3$ and m, n have different parity. We define function $f:V\longrightarrow \{-1,1\}$ such that $f(v)=-1$ if and only if

$$\begin{aligned}v \in \left\{ v_{ij}: i\equiv 1+k \pmod n , j \equiv 1+k \pmod m, 1 \le k \le \frac{mn-6}{2} \right\} . \end{aligned}$$

Likewise Case 3, for any i, j we have $\lceil \frac{m}{2} \rceil -1\le |A_i \cap V^-_f| \le \lceil \frac{m}{2}\rceil$ and $\lceil \frac{n}{2} \rceil -1 \le |B_j \cap V^-_f| \le \lceil \frac{n}{2}\rceil$ . Thus, $|N[v] \cap V^-_f |\le \frac{mn}{2} -\lfloor \frac{m}{2}\rfloor - \lfloor \frac{n}{2}\rfloor$ for any $v \in V$. So f is a signed dominating function of weight $\omega (f)=6$. Hence, $\gamma _s(K_n \times K_m) \le 6$. As above we can see $\gamma _s(K_n \times K_m) = 6$.

Case 5.:

Let $2<n <m$ are both even. Define $f:V\longrightarrow \{-1,1\}$ such that $f(v)=-1$ if and only if

$$\begin{aligned}&v \in \left\{ v_{ij}: i\equiv 1+k \pmod n , j \equiv 1+k \right. \\&\qquad \qquad \left. \pmod m, 1 \le k \le \frac{mn-8}{2}\right\} . \end{aligned}$$

With the same argument in Case 3, it is easily seen that $\gamma _s(K_n \times K_m)=8$.

$\square$

By Theorem 12 and Lemma 1, we deduce the following Corollary.

Corollary 3

For $2\le n < m$, $\gamma _s(K_n \times K_m)\ge \gamma _s(K_n)\times \gamma _s(K_m)$.