On the nonnegative signed domination numbers in graphs

Maryam Atapour^a , Seyed Mahmoud Sheikholeslami^b

m.atapour@bonabu.ac.ir, s.m.sheikholeslami@azaruniv.edu

A nonnegative signed dominating function (NNSDF) of a graph G is a function f from the vertex set V (G) to the set {−1, 1} such that P u∈N[v] f(u) ≥ 0 for every vertex v ∈ V (G). The nonnegative signed domination number of G, denoted by γ NN s (G), is the minimum weight of a nonnegative signed dominating function on G. In this paper, we establish some sharp lower bounds on the nonnegative signed domination number of graphs in terms of their order, size and maximum and minimum degree.

Keywords: nonnegative signed dominating function, nonnegative signed domination number Mathematics Subject Classification : 05C69 DOI:10.5614/ejgta.2016.4.2.10

1. Introduction

We consider finite, undirected and simple connected graphs G with vertex set V (G) = V and edge set E(G) = E. The cardinality of the vertex set of a graph G is called the order of G and is denoted by n(G) = n. For every vertex v ∈ V , the open neighborhood of v is the set N(v) = {u ∈ V | uv ∈ E} and the closed neighborhood of v is the set N[v] = N(v) ∪ {v}. The number dG(v) = d(v) = |N(v)| is the degree of the vertex v. The minimum and maximum degree of a graph G are denoted by δ(G) and ∆(G), respectively. If X ⊆ V (G), then G[X] is the subgraph of G induced by X. For disjoint subsets X and Y of vertices of a graph G, we let

Received: 1 December 2014, Revised: 18 September 2016, Accepted: 28 September 2016.

^aDepartment of Mathematics, Faculty of basic sciences, University of Bonab, Bonab, Iran

^bDepartment of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R. Iran

E(X, Y ) denote the set of edges between X and Y . For a tree T, a leaf of T is a vertex of degree 1 and a support vertex is a vertex adjacent to a leaf. The set of leaves and the set of support vertices in T are denoted by L(T) and S(T), respectively. The complement of a graph G is denoted by G. We write Kⁿ for the complete graph of order n and Cⁿ for a cycle of length n. Consult [7] for terminology and notation which are not defined here.

For a real-valued function f : V → R the weight of f is ω(f) = P v∈V f(v), and for S ⊆ V we define f(S) = P v∈S f(v), so ω(f) = f(V ). For a vertex v in V , we denote f(N[v]) by f[v]. If G is a graph, then a signed dominating function is defined in [1] as a function f : V (G) −→ {−1, 1} such that f(N[v]) ≥ 1 for all v ∈ V (G). The signed domination number γs(G) of G is the minimum weight of a signed dominating function on G. This parameter has been studied by several authors [2, 5, 6, 8, 9].

A function f : V → {−1, 1} is said to be a nonnegative signed dominating function (NNSDF) of G if f[v] ≥ 0 for every v ∈ V . The nonnegative signed domination number of G, γ NN s (G), is the minimum weight of a nonnegative signed dominating function of G. A nonnegative signed dominating function of weight γ NN s (G) is called a γ NN s (G)-function. The nonnegative signed domination number was introduced by Huang et al. [3]. In their paper, they determined the exact values of this parameter for some classes of graphs. Since every signed dominating function of G is a nonnegative signed dominating function, we conclude that

\[\gamma_s^{NN}(G) \le \gamma_s(G). \tag{1}\]

Our aim in this paper, is to establish some sharp lower bounds on the nonnegative signed domination number of graphs in terms of their order, size and maximum and minimum degree.

For any function \[f: V \to \{-1, 1\}\], we define \(P = P_f = \{v \in V \mid f(v) = 1\}\) and \(M = M_f = \{v \in V \mid f(v) = -1\}\). Then \(\omega(f) = |P| - |M| = |V(G)| - 2|M| = 2|P| - |V(G)|\).

We make use of the following results.

Observation 1.1. Let f be an NNSDF of G and let v ∈ V (G). If deg(v) is even, then f[v] ≥ 1, while f[v] ≥ 0 if deg(v) is odd.

Observation 1.2. For any even graph G, γ NN s (G) = γs(G).

Proposition A. ([3]) Let G be a graph with n vertices and m edges. Then

\[\gamma_s^{NN}(G) \ge \sqrt{4n+1} - n - 1.\]

Proposition B. ([1]) For n ≥ 3,

\[\gamma_s(C_n) = \begin{cases} n/3 & \text{if} \quad n \equiv 0 \pmod{3} \\ \lfloor \frac{n}{3} \rfloor + 1 & \text{if} \quad n \equiv 1 \pmod{3} \\ \lfloor \frac{n}{3} \rfloor + 2 & \text{if} \quad n \equiv 2 \pmod{3}. \end{cases}\]

Proposition C. ([3]) For any graph G of order n, γ NN s (G) ≡ n (mod 2).

Proposition D. ([3]) For n ≥ 1, γ NN s (Pn) = n − 2d n 3 e.

Proposition E. ([3]) Let \(K_n\) be a complete graph. Then \(\gamma_s^{NN}(K_n) = 0\) when n is even and \(\gamma_s^{NN}(K_n) = 1\) when n is odd.

Proposition 1.1. Let G be a graph of order n. Then \(\gamma_s^{NN}(G) = n\) if and only if \(G \simeq \overline{K_n}\).

Proof. One side is clear. Let \(\gamma_s^{NN}(G) = n\). If \(\deg(v) \geq 1\) for some \(v \in V(G)\), then the function \(f:V(G) \to \{-1,+1\}\) defined by f(v)=-1 and f(x)=+1 for all other vertices x, is an NNSDF of G and this implies that \(\gamma_s^{NN}(G) \le n-2\), a contradiction. Thus \(\Delta(G)=0\) and so \(G \simeq \overline{K_n}\).

Proposition 1.2. Let G be a connected graph of order n. Then \(\gamma_s^{NN}(G) = n-2\) if and only if \(G \simeq P_2, P_3, C_3, C_4 \text{ or } C_5.\)

Proof. One side is clear. Let \(\gamma_s^{NN}(G) = n-2\). We claim that \(\Delta(G) \leq 2\). Assume, to the contrary, that \(\Delta(G) \geq 3\). Let v be a vertex of maximum degree and let \(N(v) = \{v_1, \dots, v_{\Delta(G)}\}\). If \(N[v_i] \cap N[v_i] = \{v\}\) for some \(i \neq j\), then define \(f: V(G) \rightarrow \{-1, +1\}\) by \(f(v_i) = f(v_i) = -1\)and f(x) = 1 for all other vertices x. Clearly, f is an NNSDF of G with weight n - 4 which leads to a contradiction. Assume that \(N[v_i] \cap N[v_j] \neq \{v\}\) for every pair \(i, j, 1 \leq i \neq j \leq \Delta(G)\). It is easy to see that the function \(f:V(G)\to\{-1,1\}\) defined by \(f(v)=f(v_1)=-1\) and f(x) = 1 for all other vertices x, is an NNSDF of G of weight n-4 which leads to a contradiction. Therefore \(\Delta(G) \le 2\) and so G is a path or cycle. Now the result follows from Observation 1.2 and Propositions B and D.

2. Bounds on the nonnegative signed domination numbers

In this section, we establish some sharp lower bounds on the nonnegative signed domination number of graphs in terms of their order, size, maximum and minimum degree. We begin with a simple lemma.

Lemma 2.1. Let G be a graph with minimum degree \(\delta\) and maximum degree \(\Delta\) and let f be a \(\gamma_s^{NN}(G)\)-function. Then

\[|M| \left\lceil \frac{\delta+1}{2} \right\rceil \le |E(P,M)| \le |P| \left\lfloor \frac{\Delta+1}{2} \right\rfloor.\]

Proof. Let \(v \in P\). The condition \(f[v] \ge 0\) leads to \(2|N(v) \cap M| \le \deg(v) + 1\) and so \(|N(v) \cap M| \le \log(v) + 1\)\(\lfloor \frac{\deg(v)+1}{2} \rfloor \leq \lfloor \frac{\Delta+1}{2} \rfloor. \text{ It follows that } |E(P,M)]| \leq |P| \lfloor \frac{\Delta+1}{2} \rfloor.\) Now let \(v \in M\). Since \(f[v] \geq 0\), we have \(2|N(v) \cap P| \geq \deg(v) + 1\) that implies \(|N(v) \cap P| \geq \deg(v) + 1\)

\(\lceil \frac{\deg(v)+1}{2} \rceil \ge \lceil \frac{\delta+1}{2} \rceil\). This leads to \(|E(P,M)| \ge |M| \lceil \frac{\delta+1}{2} \rceil\), and the proof is complete.

Theorem 2.1. If G is a graph of order n with minimum degree \(\delta\) and maximum degree \(\Delta\), then

\[\gamma_s^{NN}(G) \ge \frac{\lceil \frac{\delta+1}{2} \rceil - \lfloor \frac{\Delta+1}{2} \rfloor}{\lceil \frac{\delta+1}{2} \rceil + \lfloor \frac{\Delta+1}{2} \rfloor} n.\]

Proof. By Lemma 2.1, \(|P|\lceil \frac{\delta+1}{2} \rceil \leq |M|\lfloor \frac{\Delta+1}{2} \rfloor\). Using this inequality and \(|P| = \frac{n+\gamma_s^{NN}(G)}{2}\) and \(|M| = \frac{n-\gamma_s^{NN}(G)}{2}\), the desired inequality follows.

We show next that the bound given in Theorem 2.1 is sharp. For this purpose, we recall the following two observations.

Observation 2.1. If k and n are integers with k < n and n is even, then we can construct a k-regular graph on n vertices.

Observation 2.2. ([2]) Let k, m and p be integers satisfying \(1 \le k \le mp\), m|k and p|k. Then there exists a bipartite graph of size k with partite sets P and M such that |P| = p and |M| = m, and each vertex in P has degree \(\frac{k}{p}\) while each vertex in M has degree \(\frac{k}{m}\).

Theorem 2.2. Let \(\delta\) and \(\Delta\) be integers with \(1 \leq \delta \leq \Delta\). Then there exists a graph G such that \(\gamma_s^{NN}(G) = \frac{\lceil \frac{\delta+1}{2} \rceil - \lfloor \frac{\Delta+1}{2} \rfloor}{\lceil \frac{\delta+1}{2} \rceil + \lfloor \frac{\Delta+1}{2} \rfloor} n\).

Proof. Let \(x=\lceil \frac{\delta+1}{2} \rceil\), \(y=\lfloor \frac{\Delta+1}{2} \rfloor\), \(\lambda=2\lceil \frac{\Delta+1}{\delta+1} \rceil\), \(m=\lambda y\), \(p=\lambda x\) and \(k=\lambda xy\). Then, \(\frac{k}{m}=x\) and \(\frac{k}{p}=y\) and so \(1\leq k\leq pm\). By Observation 2.2, there exists a bipartite graph H of size k with partite sets P and M such that |P|=p and |M|=m, and each vertex in P has degree \(\lfloor \frac{\Delta+1}{2} \rfloor\) while each vertex in M has degree \(\lceil \frac{\delta+1}{2} \rceil\). Furthermore, m is even and \(m=\lambda y>\lfloor \frac{\delta-1}{2} \rfloor\). Hence, by Observation 2.1, we can construct a \(\lfloor \frac{\delta-1}{2} \rfloor\)-regular graph with vertex set M. Similarly, p is even and \(p=\lambda x>\lceil \frac{\Delta-1}{2} \rceil\) and so we can construct a \(\lceil \frac{\Delta-1}{2} \rceil\)-regular graph with vertex set P. By adding the edges of both these graphs to P, we obtain a graph P0 in which every vertex of P1 has \(\lceil \frac{\Delta+1}{2} \rceil\) neighbors in P1 and \(\lceil \frac{\Delta-1}{2} \rceil\) neighbors in P2. In particular, every vertex in P3 has degree P4 and P5 and P7 and P8. Define P8 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P9 and P

Now we give an upper bound on the nonnegative signed domination number of a graph in terms of its order and size.

Theorem 2.3. Let G be a graph of order n and size m. Then

\[\gamma_s^{NN}(G) \ge \frac{n}{2} - m.\]

Proof. Let f be a \(\gamma_s^{NN}(G)-\) function. If \(M=\emptyset\), then the result is true. Let \(M\neq\emptyset\). It follows from \(f[v]\geq 0\) that \(|N(v)\cap P|\geq |N(v)\cap M|-1\) for each \(v\in V\). Therefore

\[2|E(G[P])| = \sum_{v \in P} |N(v) \cap P| \ge \sum_{v \in P} (|N(v) \cap M| - 1) = |E(P, M)| - |P| \tag{2}\]

that implies

\[|E(G[P])| \ge \frac{|E(P,M)| - |P|}{2}.\] (3)

It follows from Lemma 2.1 and (3) that \(|E(G[P])| \ge \frac{|M|-|P|}{2}\). Thus we have

\[m \geq |E(G[P])| + |E(P,M)| \geq \frac{3|M| - |P|}{2} = \frac{3}{2}n - 2|P| = \frac{3}{2}n - (n + \gamma_s^{NN}(G)),\]

and this leads to the desired bound.

In the next result we characterize all graphs achieving the bound in Theorem 2.3.

Theorem 2.4. Let G be a connected graph of order \(n \geq 2\) and size m. Then \(\gamma_s^{NN}(G) = \frac{n}{2} - m\) if and only if G is obtained from a connected graph H by adding \(\deg_H(v) + 1\) pendant edges at v for each \(v \in V(H)\).

Proof. Let G be the graph obtained from a connected graph H by adding \(\deg_H(v)+1\) pendant edges at v for each \(v\in V(H)\). Clearly n(G)=2n(H)+2m(H) and m(G)=n(H)+3m(H) and the function f defined by f(x)=1 for \(x\in V(H)\) and f(u)=-1 for all other vertices u, is an NNSDF of G of weight 2m(H)=n(G)/2-m(G). It follows from Theorem 2.3 that \(\gamma_s^{NN}(G)=\frac{n}{2}-m\).

Conversely, let \(\gamma_s^{NN}(G) = \frac{n}{2} - m\). Assume f is a \(\gamma_s^{NN}(G)\)-function. Then every inequality in the proof of Theorem 2.3 becomes an equality, i.e.,

• 1. \(|N(v) \cap P| = |N(v) \cap M| 1\) for each \(v \in P\),
• 2. |E(P, M)| = |M| and every vertex in M is adjacent to exactly one vertex in P,
• 3. m = |E(G[P])| + |E(P, M)|.

Let G[P] = H. It follows from (2) and (3) that M is independent and every vertex of M has degree 1. Since G is connected, we deduce that H must be connected. By (1), we conclude that every vertex \(v \in P = V(H)\) is adjacent to exactly \(\deg_H(v) + 1\) vertices in M and so v is adjacent to exactly \(\deg_H(v) + 1\) leaves. This completes the proof.

Corollary 2.1. Let G be a connected graph of order \(n \geq 2\) and size m. Then \(\gamma_s^{NN}(G) = \frac{n}{2} - m\) if and only if G is an odd graph and every vertex \(v \in V(G)\) with degree at least 3, is adjacent to \(\frac{\deg(v)+1}{2}\) leaves.

Theorem 2.5. Let G be a graph of order n, size m and minimum degree \(\delta\). Then \(\gamma_s^{NN}(G) \geq \frac{-4m+3n\lceil\frac{\delta+1}{2}\rceil-n}{3\lceil\frac{\delta+1}{2}\rceil+1}\).

Proof. Let f be a \(\gamma_s^{NN}(G)\)-function and p = |P|. By Lemma 2.1 and (2), we have

\[|E(P,M)| \ge (n-p)\lceil \frac{\delta+1}{2} \rceil.\] (4)

and

\[|E(P,M)| = \sum_{v \in P} \deg_M(v) \le \sum_{v \in P} \deg_P(v) + p = 2|E(G[P])| + p.\] (5)

It follows from (4) and (5) that

\[m \ge |E(G[P])| + |E(P,M)| \ge \frac{3(n-p)}{2} \lceil \frac{\delta+1}{2} \rceil - \frac{p}{2}.\]

Replacing \(p = \frac{n + \gamma_s^{NN}(G)}{2}\) leads to the desired bound.

Using an idea in [6], we prove the next sharp lower bound as an improvement of the bound of Theorem A for bipartite graphs.

Theorem 2.6. Let G be a bipartite graph of order n. Then

\[\gamma_s^{NN}(G) \ge 2(-1 + \sqrt{1 + 2n}) - n,\]

and this bound is sharp.

Proof. Let f be a \(\gamma_s^{NN}(G)\)-function. Let X and Y be the bipartite sets of G. Further, let \(X^+\) and \(X^-\) be the sets of vertices in X that are assigned the value +1 and -1 (under f), respectively. Let \(Y^+\) and \(Y^-\) be defined analogously. Then \(P=X^+\cup Y^+\) and \(M=X^-\cup Y^-\). For convenience, let \(|X^+|=a\), \(|X^-|=s\), \(|Y^+|=b\) and \(|Y^-|=t\). Then \(\gamma_s^{NN}(G)=2(a+b)-n\). Every vertex in \(Y^-\) must be adjacent to at least one vertex in \(X^+\). Therefore, by the pigeonhole principle, there is a vertex v in \(X^+\) adjacent to at least \(\frac{|Y^-|}{|X^+|}=\frac{t}{a}\) vertices in \(Y^-\). Then

\[0 \le f(N[v]) \le |Y^+| - \frac{|Y^-|}{|X^+|} = b - \frac{t}{a}\]

i.e.,

\[ab > t\]. (6)

By a similar argument, one may show that

\[ab \ge s.\] (7)

Adding (6) and (7), we obtain that

\[2ab \ge t + s. \tag{8}\]

By the fact \(2ab \leq \frac{(a+b)^2}{2}\) together with (8), we have \(\frac{(a+b)^2}{2} \geq 2ab \geq s+t=n-(a+b)\) which implies that \(a+b \geq -1+\sqrt{1+2n}\). Thus \(\gamma_s^{NN}(G)=2(a+b)-n \geq 2(-1+\sqrt{1+2n})-n\).

Now, for \(k \geq 1\), let a = b = k, \(t = s = k^2\) and let \(G_k\) be a graph of order \(n = 2k + 2k^2 = 2a + 2a^2\) obtained from the disjoint union of \(K_{a,a}\) with the partite sets X and Y, \(\overline{K_t}\) and \(\overline{K_s}\) by adding edges between X and \(V(\overline{K_t})\), and edges between Y and \(V(\overline{K_s})\) so that each vertex in \(\overline{K_t}\) joined to exactly one vertex in X, each vertex in X joined to exactly k vertices in \(\overline{K_t}\), each vertex in \(\overline{K_t}\) joined to exactly one vertex in Y and each vertex in Y joined to exactly K vertices in \(\overline{K_s}\). Then the function \(f:V(G_k) \longrightarrow \{-1,+1\}\) that assigns \(K_t\) to every vertex of \(K_t\) and \(K_t\) and \(K_t\) the others is an NNSDF of \(K_t\) with weight \(K_t\) and \(K_t\) in \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) and \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) are \(K_t\) are \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) are \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) are \(K_t\) and \(K_t\) are \(K_t\) are \(K_t\) are \(K_t\) are \(K_t\) are \(K_t\) are \(K_t\) are \(K_t\) are \(K_t\) are \(K_t\) are \(K_t\) are \(K_t\) are \(K_\)

The next result gives an upper bound on the nonnegative signed domination number of a graph in terms of it's degree sequence.

Theorem 2.7. Let G be a graph of order n, with degree sequence \(d_1 \geq d_2 \geq \ldots \geq d_n\). If G has \(n_{even}\) vertices of even degree, and if k is the smallest integer for which \(\sum_{i=1}^k d_i - \sum_{i=k+1}^n d_i \geq n_{even} + n - 2k\), then \(\gamma_s^{NN}(G) \geq 2k - n\). Furthermore, this bound is sharp.

Proof. Let f be a γ NN s (G)-function and p = |P|. By Observation 1.1, we have

\[n_{even} \leq \sum_{v \in V} \sum_{u \in N(v)} f(u) = \sum_{v \in V} (\deg(v) + 1) f(v)\] \[= \sum_{v \in P} \deg(v) - \sum_{v \in M} \deg(v) + |P| - |M| \leq \sum_{i=1}^{p} d_i - \sum_{i=p+1}^{n} d_i + 2p - n.\]

It follows from the choice of k that p ≥ k and so γ NN s (G) = 2p − n ≥ 2k − n.

To prove the sharpness, let G be the graph obtained from the path P^k := v1, v2, . . . , vk, k ≥ 3, by adding the new vertices x1, . . . , xk, y1, . . . , yk, z2, . . . , zk−¹ and joining vⁱ to xⁱ , yⁱ for 1 ≤ i ≤ k and vⁱ to zⁱ for 2 ≤ i ≤ k − 1. Obviously the degree sequence of G is 5, . . . , 5 | {z } k−2 , 3, 3 1 . . . , 1 | {z } 3k−2 . It is

easy to verify that k is the smallest positive integer such that P k i=1 dⁱ − Pn i=k+1 dⁱ ≥ n + neven − 2k implying that γ NN s (G) ≥ 2k − n = −2k + 2. Now define f : V (G) → {−1, 1} by f(v) = +1 if v ∈ V (Pk) and f(v) = −1 for all other vertices v. It is easy to see that f is an NNSDF of G that implies γ NN s (G) ≤ ω(f) = −2k + 2. This completes the proof.

References

• [1] J.E. Dunbar, S.T. Hedetniemi, M.A. Henning and P.J. Slater, Signed domination in graphs, Graph Theory, Combinatorics and Application, John Wiley & Sons, Inc. 1 (1995), 311–322.
• [2] M.A. Henning, Signed total domination in graphs, Discrete Math. 278 (2004), 109–125.
• [3] Z. Huang, Z. Feng and H. Xing, On nonnegative signed domination in graphs and its algorithmic complexity, J. Networks 8 (2013), 365–372.
• [4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (Eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
• [5] H. Karami, R. Khoeilar, S.M. Sheikholeslami and A. Khodkar, Global signed domination in graphs, Bull. Malays. Math. Sci. Soc. 36 (2013), 363–372.
• [6] C. Wang, The signed k-domination numbers in graphs, Ars Combin. 106 (2012), 205–211.
• [7] D.B. West, Introduction to Graph Theory, Prentice-Hall, Inc, 2000.
• [8] B. Zelinka, Signed domination number of a graph, Czechoslovak Math. J. 51 (2001), 225– 229.
• [9] Z. Zhang, B. Xu, Y. Li and L. Liu, A note on the lower bounds of signed domination number of a graph, Discrete Math. 195 (1999), 295–298.