Lower bounds on nonnegative signed domination parameters in graphs

Abstract

Let $1\le k\le n$ be a positive integer. A nonnegative signed $k$-subdominating function is a function $f:V\left(G\right)\to \{-1,1\}$ satisfying ${\sum }_{u\in N_G\left[v\right]}f\left(u\right)\ge 0$ for at least $k$ vertices $v$ of $G$. The value $min{\sum }_{v\in V\left(G\right)}f\left(v\right)$, taking over all nonnegative signed $k$-subdominating functions $f$ of $G$, is called the nonnegative signed $k$-subdomination number of $G$ and denoted by ${\gamma }_{ks}^{NN}\left(G\right)$. If $k=\left|V\left(G\right)\right|$, then ${\gamma }_{ks}^{NN}\left(G\right)={\gamma }_s^{NN}\left(G\right)$ is the nonnegative signed domination number, introduced in Huang et al. (2013) . In this paper, we obtain several sharp lower bounds of ${\gamma }_s^{NN}\left(G\right)$, which extend some known lower bounds on ${\gamma }_s^{NN}\left(G\right)$.

We also initiate a study of the nonnegative signed $k$-subdomination number in graphs and establish some sharp lower bounds for ${\gamma }_{ks}^{NN}\left(G\right)$ in terms of the order and the degree sequence of a graph $G$.

Keywords:

• Nonnegative signed domination number
• Nonnegative signed $k$-subdomination number

1 Introduction

Let $G$ be a simple graph of order $n$ with vertex set $V\left(G\right)$ and size $m$ with edge set $E\left(G\right)$. We use [1] for terminology and notation, which are not defined here. If $X\subseteq V\left(G\right)$, then $G\left[X\right]$ is the subgraph of $G$ induced by $X$. For disjoint subsets $X$ and $Y$ of vertices we let $E(X,Y)$ denote the set of edges between $X$ and $Y$.

The open neighborhood $N_G\left(v\right)$ of a vertex $v\in V\left(G\right)$ is the set of all vertices adjacent to $v$. Its closed neighborhood is $N_G\left[v\right]=N_G\left(v\right)\cup \left\{v\right\}$. In addition, the open and closed neighborhoods of a subset $S\subseteq V\left(G\right)$ are $N_G\left(S\right)={\cup }_{v\in S}{N}_G\left(v\right)$ and $N_G\left[S\right]=N_G\left(S\right)\cup S$, respectively. The degree of a vertex $v\in V\left(G\right)$ is ${deg}_G\left(v\right)=\mid N_G\left(v\right)\mid$. The minimum and maximum degrees in graph $G$ are denoted by $\delta \left(G\right)$ and $\Delta \left(G\right)$, respectively. A vertex $v\in V\left(G\right)$ is called an odd (even) vertex if ${deg}_G\left(v\right)$ is odd (even). For a graph $G=(V,E)$, let $V_o$ ( $V_e$) be the set of odd (even) vertices with $n_o=\mid V_o\mid$ and $n_e=\mid V_e\mid$.

For a real-valued function $f:V\left(G\right)⟶\mathbb{R}$ the weight of $f$ is $\omega \left(f\right)={\sum }_{v\in V\left(G\right)}f\left(v\right)$ and for a subset $S$ of $V\left(G\right)$ we define $f\left(S\right)={\sum }_{v\in S}f\left(v\right)$, so $\omega \left(f\right)=f\left(V\left(G\right)\right)$. For a positive integer $1\le k\le n$, a signed$k$-subdominating function (SkSDF) of G is a function $f:V\left(G\right)⟶\{-1,1\}$ such that $f\left(N_G\left[v\right]\right)\ge 1$ for at least $k$ vertices $v$ of $G$. The signed$k$-subdomination number for a graph $G$ is defined as ${\gamma }_{ks}\left(G\right)=min\left\{w\left(f\right)\right|f\text{is a SkSDF of}G\}$. The signed $k$-subdomination number was introduced and studied by Cockayne and Mynhardt [2]. In the special case where $k=n$, ${\gamma }_{ks}\left(G\right)$ is the signed domination number ${\gamma }_s\left(G\right)$. This concept has been extensively explored in the literature; see e.g. [3–5].

A nonnegative signed dominating function (NNSDF) of $G$ is defined in [6] as a function $f:V\left(G\right)⟶\{-1,1\}$ such that $f\left(N_G\left[v\right]\right)\ge 0$ for all vertices $v$ of $G$. The nonnegative signed domination number (NNSDN) of $G$ is ${\gamma }_s^{NN}\left(G\right)=min\left\{\omega \left(f\right)\right|f\text{is an NNSDF of}G\}$.

We now introduce a nonnegative signed$k$-subdominating function (NNSkSDF) of $G$ for a positive integer $1\le k\le n$ as a function $f:V\left(G\right)⟶\{-1,1\}$ such that $f\left(N_G\left[v\right]\right)\ge 0$ for at least $k$ vertices $v$ of $G$. We define the nonnegative signed $k$-subdomination number (NNSkSDN) of $G$ by ${\gamma }_{ks}^{NN}\left(G\right)=min\{\omega \left(f\right)\mid f\text{is a NNS}k\text{SDF of}G\}$. A nonnegative signed $k$-subdominating function of weight ${\gamma }_{ks}^{NN}\left(G\right)$ is called a ${\gamma }_{ks}^{NN}\left(G\right)$-function. Note that ${\gamma }_{ns}^{NN}\left(G\right)={\gamma }_s^{NN}\left(G\right)$. Since every signed $k$-subdominating function of $G$ is a nonnegative signed $k$-subdominating function, we deduce that $${\gamma }_{ks}^{NN}\left(G\right)\le {\gamma }_{ks}\left(G\right).$$For a function $f:V\left(G\right)⟶\{-1,1\}$ of $G$ we define $P=\{v\in V\left(G\right)\mid f\left(v\right)=1\}$, $M=\{v\in V\left(G\right)\mid f\left(v\right)=-1\}$, and $C_f=\{v\in V\left(G\right)|f\left(N_G\left[v\right]\right)\ge 0\}$.

In this paper, we establish some new lower bounds on ${\gamma }_s^{NN}\left(G\right)$ for a general graph in terms of different graph parameters. Some of these bounds improve several lower bounds on ${\gamma }_s^{NN}\left(G\right)$ presented in [6,7]. We also initiate a study of nonnegative signed $k$-subdomination numbers in graphs, and present some sharp lower bounds for ${\gamma }_{ks}^{NN}\left(G\right)$ in terms of the order and the degree sequence of $G$.

Observation 1

Let $f$ be an NNSDF of $G$. For $v\in V\left(G\right)$ if$v$ is an even vertex, then $f\left(N_G\left[v\right]\right)\ge 1$ while $f\left(N_G\left[v\right]\right)\ge 0$ if$v$ is an odd vertex.

In this paper, we make use of the following results.

Theorem A

[7] Let $G$ be a graph of order $n$ and size $m$. Then $${\gamma }_s^{NN}\left(G\right)\ge \frac{n}{2}-m.$$

Theorem B

[7] Let $G$ be a graph of order $n$, size$m$ and minimum degree $\delta$. Then $${\gamma }_s^{NN}\left(G\right)\ge \frac{-4m+3n\lceil \frac{\delta +1}{2}\rceil -n}{3\lceil \frac{\delta +1}{2}\rceil +1}.$$

Theorem C

[4] For $n\ge 3$, $${\gamma }_s\left(C_n\right)=\left\{\begin{array}{ccc}n∕3\hfill & \hfill \text{if}\hfill & n\equiv 0(mod3),\hfill \\ \lfloor \frac{n}{3}\rfloor +1\hfill & \hfill \text{if}\hfill & n\equiv 1(mod3),\hfill \\ \lfloor \frac{n}{3}\rfloor +2\hfill & \hfill \text{if}\hfill & n\equiv 2(mod3).\hfill \end{array}\right.$$

Corollary 2

[8] For any $r$-regular graph $G$ of order $n$,${\gamma }_s\left(G\right)\ge \frac{n}{r+1}$, for$r$ even. Furthermore this bound is sharp.

Proposition 3

[6] Let $K_n$ be a complete graph. Then ${\gamma }_s^{NN}\left(K_n\right)=0$ when $n$ is even and ${\gamma }_s^{NN}\left(K_n\right)=1$ when $n$ is odd.

Theorem D

[6] For any graph $G$ with maximum degree $\Delta$ and minimum degree $\delta$, we have $${\gamma }_s^{NN}\left(G\right)\ge \frac{\delta -\Delta }{\delta +\Delta +2}n.$$

2 Lower bounds on the NNSDNs of graphs

In this section, we present some new sharp lower bounds for ${\gamma }_s^{NN}\left(G\right)$ in terms of $n_e$ where $n_e$ is the number of even vertices in a graph $G$. We begin with the following lemma.

Lemma 4

Let $f$ be an NNSDF of a simple connected graph $G$. Then,

1.	${\sum }_{v\in P}{deg}_G\left(v\right)\ge n+n_e-2\mid P\mid +{\sum }_{v\in M}{deg}_G\left(v\right)$.
2.	${\sum }_{v\in P}{deg}_{G\left[P\right]}\left(v\right)\ge {\sum }_{v\in P}\lceil \frac{{deg}_G\left(v\right)-1}{2}\rceil$.

Proof

For $v\in V\left(G\right)$, let ${deg}_P\left(v\right)$ and ${deg}_M\left(v\right)$ denote the numbers of vertices of $P$ and $M$, respectively, which are adjacent to $v$. Clearly, ${deg}_G\left(v\right)={deg}_M\left(v\right)+{deg}_P\left(v\right)$. Since $f\left(N_G\left[v\right]\right)\ge 0$, for every $v\in P$, ${deg}_M\left(v\right)\le {deg}_P\left(v\right)+1$, and for every $v\in M$, ${deg}_P\left(v\right)\ge {deg}_M\left(v\right)+1$. Hence, if $v\in P$, then ${deg}_M\left(v\right)\le \lfloor \frac{{deg}_G\left(v\right)+1}{2}\rfloor$ and if $v\in M$, then ${deg}_P\left(v\right)\ge \lceil \frac{{deg}_G\left(v\right)+1}{2}\rceil$.

1.

Counting the number of edges in $E(P,M)$ in two ways, we can deduce that $$\begin{array}{ccccc}\hfill \sum _{v\in M}\lceil \frac{{deg}_G\left(v\right)+1}{2}\rceil \hfill & \hfill \le \hfill & \hfill \left|E(P,M)\right|\hfill & \hfill \le \hfill & \sum _{v\in P}\lfloor \frac{{deg}_G\left(v\right)+1}{2}\rfloor .\hfill \end{array}$$It follows that $$\begin{array}{ccc}\hfill \sum _{v\in P}{deg}_G\left(v\right)+\mid P\mid \hfill & \hfill \ge \hfill & \sum _{v\in V}\lceil \frac{{deg}_G\left(v\right)+1}{2}\rceil \hfill \\ \hfill \hfill & \hfill =\hfill & \sum _{v\in V_o}\frac{{deg}_G\left(v\right)+1}{2}+\sum _{v\in V_e}\frac{{deg}_G\left(v\right)+2}{2}\hfill \\ \hfill \hfill & \hfill =\hfill & \sum _{v\in V}\frac{{deg}_G\left(v\right)}{2}+\frac{n_o}{2}+n_e\hfill \\ \hfill \hfill & \hfill =\hfill & \sum _{v\in P}\frac{{deg}_G\left(v\right)}{2}+\sum _{v\in M}\frac{{deg}_G\left(v\right)}{2}+\frac{n_o}{2}+n_e,\hfill \end{array}$$ which implies that $$\sum _{v\in P}\frac{{deg}_G\left(v\right)}{2}\ge \sum _{v\in M}\frac{{deg}_G\left(v\right)}{2}+\frac{n_o}{2}+n_e-\mid P\mid .$$Hence, $$\begin{array}{ccc}\hfill \sum _{v\in P}{deg}_G\left(v\right)\hfill & \hfill \ge \hfill & \sum _{v\in M}{deg}_G\left(v\right)+n+n_e-2\mid P\mid .\hfill \end{array}$$

2.

Consider the subgraph $G\left[P\right]$ induced by $P$. We have ${deg}_{G\left[P\right]}\left(v\right)={deg}_P\left(v\right)$ for each $v\in P$. Since ${deg}_P\left(v\right)\ge \lceil \frac{{deg}_G\left(v\right)-1}{2}\rceil$ for each $v\in P$, we have $$\sum _{v\in P}{deg}_{G\left[P\right]}\left(v\right)\ge \sum _{v\in P}\lceil \frac{{deg}_G\left(v\right)-1}{2}\rceil .\square$$

In the next theorem we present some lower bounds on ${\gamma }_s^{NN}\left(G\right)$. By using Lemma 4 and graph parameters such as order, size, number of even vertices, maximum and minimum degrees we obtain some new lower bounds for ${\gamma }_s^{NN}\left(G\right)$.

Theorem 5

Let $G$ be a simple connected graph of order $n$, minimum degree $\delta$, maximum degree $\Delta$ and the number of even vertices $n_e$. Then

1.	${\gamma }_s^{NN}\left(G\right)\ge \frac{n\delta -n\Delta +2n_e}{\Delta +\delta +2}$,
2.	${\gamma }_s^{NN}\left(G\right)\ge \frac{2m+n_e-n\Delta }{\Delta +1}$,
3.	${\gamma }_s^{NN}\left(G\right)\ge \frac{n\delta +n_e-2m}{\delta +1}$,
4.	${\gamma }_s^{NN}\left(G\right)\ge \lceil \frac{-(\delta +1)+\sqrt{{(\delta +1)}^2+8(n\delta +n+n_e)}}{2}-n\rceil$,
5.	${\gamma }_s^{NN}\left(G\right)\ge \lceil \sqrt{2m+n+n_e}-n\rceil$.

Proof

Let $f$ be a ${\gamma }_s^{NN}\left(G\right)$-function. Let $P=\{v\in V\left(G\right)|f\left(v\right)=1\}$ and $M=\{v\in V\left(G\right)|f\left(v\right)=-1\}$.

1.	Since $\delta \le {deg}_G\left(v\right)\le \Delta$ for each $v\in V\left(G\right)$, according to Lemma 4(1) we have $$\delta n-\mid P\mid \delta +n+n_e-2\mid P\mid \le \sum _{v\in P}{deg}_G\left(v\right)\le \Delta \mid P\mid .$$It leads to $$\mid P\mid \ge \frac{\delta n+n+n_e}{\Delta +\delta +2}.$$Hence, $${\gamma }_s^{NN}\left(G\right)=2\mid P\mid -n\ge \frac{n\delta -n\Delta +2n_e}{\Delta +\delta +2}.$$
2.	Since $2m={\sum }_{v\in V}{deg}_G\left(v\right)$ and ${deg}_G\left(v\right)\le \Delta$ for each $v\in V\left(G\right)$, by Lemma 4(1) it follows that $$\begin{array}{ccc}\hfill 2m+n+n_e-2\mid P\mid \hfill & \hfill =\hfill & \sum _{v\in V}{deg}_G\left(v\right)+n+n_e-2\mid P\mid \hfill \\ \hfill \hfill \\ \hfill \hfill & \hfill \le \hfill & 2\sum _{v\in P}{deg}_G\left(v\right)\hfill \\ \hfill \hfill \\ \hfill \hfill & \hfill \le \hfill & 2\Delta \mid P\mid .\hfill \end{array}$$Therefore, $2\mid P\mid \ge \frac{2m+n+n_e}{\Delta +1}$, and ${\gamma }_s^{NN}\left(G\right)\ge \frac{2m+n_e-n\Delta }{\Delta +1}$, as desired.
3.	Using Lemma 4(1), the facts $2m={\sum }_{v\in V}{deg}_G\left(v\right)$ and ${deg}_G\left(v\right)\ge \delta$ for any $v\in V\left(G\right)$, we have $$\begin{array}{ccc}\hfill 2m\hfill & \hfill =\hfill & \sum _{v\in V}{deg}_G\left(v\right)\hfill \\ \hfill \hfill & \hfill \ge \hfill & 2\sum _{v\in M}{deg}_G\left(v\right)+n+n_e-2\mid P\mid \hfill \\ \hfill \hfill & \hfill \ge \hfill & 2n\delta -2\delta \mid P\mid +n+n_e-2\mid P\mid \hfill \end{array}$$It follows that $$2\mid P\mid \ge \frac{2n\delta +n+n_e-2m}{\delta +1}.$$Thus, ${\gamma }_s^{NN}\left(G\right)\ge \frac{n\delta +n_e-2m}{\delta +1}$.
4.	Consider $G\left[P\right]$ as the induced subgraph of $G$ by $P$. According to Lemma 4(2), we have $$\sum _{v\in P}{deg}_{G\left[P\right]}\left(v\right)\ge \sum _{v\in P}\lceil \frac{{deg}_G\left(v\right)-1}{2}\rceil \ge \sum _{v\in P}\frac{{deg}_G\left(v\right)-1}{2}.$$On the other hand, since $G\left[P\right]$ is a simple connected graph, $$\sum _{v\in P}{deg}_{G\left[P\right]}\left(v\right)\le \mid P\mid (\mid P\mid -1).$$Thus, $$\begin{array}{ccc}\hfill 2\mid P\mid (\mid P\mid -1)\hfill & \hfill \ge \hfill & \sum _{v\in P}{deg}_G\left(v\right)-\mid P\mid \hfill \\ \hfill \hfill & \hfill \ge \hfill & \sum _{v\in M}{deg}_G\left(v\right)+n+n_e-3\mid P\mid \hfill \\ \hfill \hfill & \hfill \ge \hfill & n\delta -\delta \mid P\mid +n+n_e-3\mid P\mid .\hfill \end{array}$$This implies that $$2\mid P{\mid }^2+(\delta +1)\mid P\mid -(n\delta +n+n_e)\ge 0.$$Therefore, $$2\mid P\mid \ge \frac{-(\delta +1)+\sqrt{{(\delta +1)}^2+8(n\delta +n+n_e)}}{2},$$ and hence ${\gamma }_s^{NN}\left(G\right)\ge \lceil \frac{-(\delta +1)+\sqrt{{(\delta +1)}^2+8(n\delta +n+n_e)}}{2}-n\rceil$, as desired.
5.	By Parts (4) and (2) we have $$2\sum _{v\in P}{deg}_G\left(v\right)\le 4\mid P{\mid }^2-2\mid P\mid ,$$and $$2\sum _{v\in P}{deg}_G\left(v\right)\ge 2m+n+n_e-2\mid P\mid ,$$respectively. So, $$4\mid P{\mid }^2\ge 2m+n+n_e,$$It leads to $$\mid P\mid \ge \frac{\sqrt{2m+n+n_e}}{2}.$$Thus, ${\gamma }_s^{NN}\left(G\right)\ge \lceil \sqrt{2m+n+n_e}-n\rceil$. This completes the proof. □

From Theorem 5(1)$-$ (3), we have the following result.

Corollary 6

For $r\ge 1$, if $G$ is an$r$-regular graph of order $n$, then $${\gamma }_s^{NN}\left(G\right)\ge \left\{\begin{array}{cc}\frac{n}{r+1}\hfill & \text{if}r\text{is even,}\hfill \\ 0\hfill & \text{if}r\text{is odd}.\hfill \end{array}\right.$$Furthermore, these bounds are sharp.

For $k=n$ by Observation 1 when $r$ is even, we have the same bound presented in Corollary 2 by Henning. In order to show that the bounds presented in Theorem 5 are sharp, we will give a graph $G$ and construct a ${\gamma }_s^{NN}\left(G\right)$-function $f$ such that $w\left(f\right)$ achieves the lower bounds. Our bounds for some of these graphs are attainable while the corresponding bounds given in Theorems A, B, and D are not. In fact, trivial examples such as $G\in \{K_n,C_n\}$ are sufficient for this. By Proposition 3 it is easy to see that ${\gamma }_s^{NN}\left(K_n\right)$ attains all the five bounds in Theorem 5 while the bound in Theorem A shows that ${\gamma }_s^{NN}\left(K_n\right)\ge \frac{2n-n^2}{2}$ and the bound in Theorem B is not more than $\frac{5n-n^2}{3n+5}$. Moreover, by Theorem C, ${\gamma }_s^{NN}\left(C_n\right)$ attains the lower bounds in Theorem 5(1)$-$ (3), when $n\equiv 0\left(mod3\right)$ while the bounds in Theorems A, B and D are not more than $\frac{n}{7}$. Besides, we can construct a non-complete graph with an arbitrary large order which attains the lower bounds in Theorem 5(1)$-$ (3) as follows. Letting $t$ be a positive integer, we consider a cycle of length $2t$. For every edge, we include an additional vertex being adjacent to both endpoints of the corresponding edge. The obtained graph is denoted by $G$. It is easy to check that $G$ is a graph with $n=4t$, $m=6t$, $\delta =2$, $\Delta =4$ and $n_e=4t$. Define a function $f:V\left(G\right)⟶\{-1,1\}$ as follows: $f\left(v\right)=1$ for $v\in V\left(C_{2t}\right)$ and $f\left(v\right)=-1$ for $v\in V\left(G\right)\setminus V\left(C_{2t}\right)$. It is easy to verify that $f$ is a ${\gamma }_s^{NN}\left(G\right)$-function with $w\left(f\right)=0$ and bounds in Theorem 5(1)$-$ (3) are also $0$, which implies that $G$ is sharp for these bounds. However, ${\gamma }_s^{NN}\left(G\right)$ does not attain the corresponding bounds given in Theorems A, B and D, which are $-4t$, $\lceil -\frac{4t}{7}\rceil$, and $-t$, respectively. Next, we show that there is also a graph $G$ different from $K_n$ such that ${\gamma }_s^{NN}\left(G\right)$ reaches lower bounds in Theorem 5(4)$-$ (5). Let $H$ be the Hajós graph. We can verify that ${\gamma }_s^{NN}\left(H\right)=0$, and $H$ is sharp for presented bounds in Theorem 5(4)$-$ (5).

3 Lower bounds on the NNSkSDNs of graphs

In this section, we initiate a study of the nonnegative signed $k$-subdomination number in graphs. we present some lower bounds on the nonnegative signed $k$-subdomination number of a graph in terms of the order and the degree sequence. We begin with the following lemma.

Lemma 7

Let $G$ be a graph and $1\le k\le n$ be a positive integer. Let $f$ be a ${\gamma }_{ks}^{NN}\left(G\right)$-function. Let $P_1=P\cap C_f$,$P_2=P\setminus P_1$,$M_1=M\cap C_f$ and$M_2=M\setminus M_1$. Then, $$\sum _{v\in P}{deg}_G\left(v\right)+\mid P_1\mid \ge \sum _{v\in P_1\cup M_1}\lceil \frac{{deg}_G\left(v\right)+1}{2}\rceil .$$

Proof

Note that if $v\in V\left(G\right)$, then ${deg}_G\left(v\right)={deg}_P\left(v\right)+{deg}_M\left(v\right)$. For $v\in P_1\cup M_1$, $f\left(N_G\left[v\right]\right)\ge 0$. So, if $v\in P_1$, then ${deg}_P\left(v\right)\ge \lceil \frac{{deg}_G\left(v\right)-1}{2}\rceil$ and ${deg}_M\left(v\right)\le \lfloor \frac{{deg}_G\left(v\right)+1}{2}\rfloor$. Similarly, if $v\in M_1$, then ${deg}_P\left(v\right)\ge \lceil \frac{{deg}_G\left(v\right)+1}{2}\rceil$ and ${deg}_M\left(v\right)\le \lfloor \frac{{deg}_G\left(v\right)-1}{2}\rfloor$.

Counting the number of edges in $E(P,M)$ in two ways, we conclude that $$\sum _{v\in M_1}\lceil \frac{{deg}_G\left(v\right)+1}{2}\rceil +\sum _{v\in M_2}{deg}_P\left(v\right)\le \sum _{v\in P_1}\lfloor \frac{{deg}_G\left(v\right)+1}{2}\rfloor +\sum _{v\in P_2}{deg}_M\left(v\right).$$By adding ${\sum }_{v\in P_1}\lceil \frac{{deg}_G\left(v\right)+1}{2}\rceil$ to the both sides of the inequality we have $$\begin{array}{ccc}\hfill \sum _{v\in P}{deg}_G\left(v\right)+\mid P_1\mid & \hfill \ge \hfill & \sum _{v\in P_1\cup M_1}\lceil \frac{{deg}_G\left(v\right)+1}{2}\rceil +\sum _{v\in M_2}{deg}_G\left(v\right)\hfill \\ \hfill & \hfill \ge \hfill & \sum _{v\in P_1\cup M_1}\lceil \frac{{deg}_G\left(v\right)+1}{2}\rceil ,\hfill \end{array}$$and this completes the proof.□

Theorem 8

For any graph $G$ with degree sequence $d_1\le d_2\le \cdots \le d_n$ and any positive integer $1\le k\le n$,

1.	${\gamma }_{ks}^{NN}\left(G\right)\ge \frac{2{\sum }_{i=1}^k\lceil \frac{d_i+1}{2}\rceil }{\Delta +1}-n$.
2.	${\gamma }_{ks}^{NN}\left(G\right)\ge \frac{n\delta -4m-n+2{\sum }_{i=1}^k\lceil \frac{d_i+1}{2}\rceil }{\delta +1}$.

Furthermore, these bounds are sharp.

Proof

Let $f$ be a ${\gamma }_{ks}^{NN}\left(G\right)$-function. Let $P_1=P\cap C_f$ and $M_1=M\cap C_f$.

1.

Since $\delta \le {deg}_G\left(v\right)\le \Delta$ for each $v\in V\left(G\right)$, Lemma 7 follows that $$\Delta \mid P\mid +\mid P\mid \ge \sum _{v\in P}{deg}_G\left(v\right)+\mid P_1\mid \ge \sum _{v\in P_1\cup M_1}\lceil \frac{{deg}_G\left(v\right)+1}{2}\rceil .$$Note that $P_1\cap M_1=0̸$ and $\mid P_1\cup M_1\mid =\mid P_1\mid +\mid M_1\mid \ge k$. So, $$\mid P\mid \ge \frac{\sum _{v\in P_1\cup M_1}\lceil \frac{{deg}_G\left(v\right)+1}{2}\rceil }{\Delta +1}\ge \frac{\sum _{i=1}^k\lceil \frac{d_i+1}{2}\rceil }{\Delta +1}.$$Thus, $${\gamma }_{ks}^{NN}\left(G\right)=2\mid P\mid -n\ge \frac{2\sum _{i=1}^k\lceil \frac{d_i+1}{2}\rceil }{\Delta +1}-n.$$

2.

Obviously, $2m={\sum }_{v\in V\left(G\right)}{deg}_G\left(v\right)={\sum }_{v\in P}{deg}_G\left(v\right)+{\sum }_{v\in M}{deg}_G\left(v\right)$. If we add $\mid P_1\mid$ to the both sides of this equality, then by Lemma 7 we deduce that $$\begin{array}{ccc}\hfill \mid P\mid \ge \mid P_1\mid & \hfill \ge \hfill & -2m+\sum _{v\in P_1\cup M_1}\lceil \frac{{deg}_G\left(v\right)+1}{2}\rceil +\sum _{v\in M}{deg}_G\left(v\right)\hfill \\ \hfill & \hfill \ge \hfill & -2m+\sum _{i=1}^k\lceil \frac{d_i+1}{2}\rceil +\delta n-\delta \mid P\mid .\hfill \end{array}$$Therefore, $$\mid P\mid \ge \frac{n\delta -2m+\sum _{i=1}^k\lceil \frac{d_i+1}{2}\rceil }{\delta +1},$$and hence, $${\gamma }_{ks}^{NN}\left(G\right)=2\mid P\mid -n\ge \frac{n\delta -4m-n+2\sum _{i=1}^k\lceil \frac{d_i+1}{2}\rceil }{\delta +1}.$$

Now suppose that $k=n$, considering that $2{\sum }_{i=1}^n\lceil \frac{d_i+1}{2}\rceil =2m+n+n_e$, we can immediately obtain those two bounds in Theorem 5(2) and (3) from the lower bounds of Theorem 8, respectively. Since lower bounds presented in Theorem 5 are sharp, so there exist graphs whose ${\gamma }_{ks}^{NN}\left(G\right)$ receive lower bounds in Theorem 8. Therefore, these bounds are sharp.□

From Theorem 8(1) or (2) the following result can be immediately deduced.

Corollary 9

For $r\ge 1$, if $G$ is an$r$-regular graph of order $n$, then $${\gamma }_{ks}^{NN}\left(G\right)\ge \left\{\begin{array}{cc}\frac{k(r+2)}{r+1}-n\hfill & \text{if}r\text{is even,}\hfill \\ k-n\hfill & \text{if}r\text{is odd}.\hfill \end{array}\right.$$Furthermore, these bounds are sharp.