On the signed 2-independence number of graphs

S.M. Hosseini Moghaddam^a , D.A. Mojdeh^b , Babak Samadi^b , Lutz Volkmann^c

sm.hosseini1980@yahoo.com, damojdeh@umz.ac.ir, samadibabak62@gmail.com, volkm@math2.rwth-aachen.de

In this paper, we study the signed 2-independence number in graphs and give new sharp upper and lower bounds on the signed 2-independence number of a graph by a simple uniform approach. In this way, we can improve and generalize some known results in this area.

Keywords: domination number, limited packing, tuple domination, signed 2-independence number Mathematics Subject Classification : 05C69 DOI:10.5614/ejgta.2017.5.1.4

1. Introduction

Throughout this paper, let G be a finite connected graph with vertex set V = V (G) and edge set E = E(G). We use [13] as a reference for terminology and notation which are not defined here. The open neighborhood of a vertex v is denoted by N(v), and the closed neighborhood of v is N[v] = N(v) ∪ {v}. The minimum and maximum degree of G are respectively denoted by ∆(G) = ∆ and δ(G) = δ.

Let S ⊆ V . For a real-valued function f : V → R we define f(S) = P v∈S f(v). Also, f(V ) is the weight of f. A signed 2-independence function, abbreviated S2IF, of G is defined in [14] as a function f : V → {−1, 1} such that f(N[v]) ≤ 1, for every v ∈ V . The signed 2-independence number, abbreviated S2IN, of G is α 2 s (G) = max{f(V )|f is a S2IF of G}. This concept was

Received: 9 January 2015, Revised 15 January 2017, Accepted: 26 January 2017.

^aQom Azad University, Qom, Iran

^bDepartment of Mathematics, University of Mazandaran, Babolsar, Iran

^cLehrstuhl II fur Mathematik, RWTH Aachen University, 52056 Aachen, Germany ¨

defined in [14] as a certain dual of the signed domination number of a graph [3] and has been studied by several authors including [8, 10, 11, 12].

A set \(S \subseteq V\) is a dominating set if each vertex in \(V \setminus S\) has at least one neighbor in S. The domination number \(\gamma(G)\) is the minimum cardinality of a dominating set [7]. A subset \(B \subseteq V\) is a 2-packing in G if for every pair of vertices \(u, v \in B\), \(d(u, v) \geq 3\). The 2-packing number (or packing number) \(\rho(G)\) is the maximum cardinality of a 2-packing in G.

Gallant et al. [5] introduced the concept of limited packing in graphs. They exhibited some real-world applications of it to network security, NIMBY, market saturation and codes. In this paper we exhibit an application of it to signed 2-independence number in graphs. In fact as it is defined in [5], a set of vertices \(B \subseteq V\) is called a k-limited packing in G provided that for all \(v \in V\), we have \(|N[v] \cap B| \leq k\). The limited packing number, denoted \(L_k(G)\), is the largest number of vertices in a k-limited packing set. It is easy to see that \(L_1(G) = \rho(G)\). In [6], Harary and Haynes introduced the concept of tuple domination in graphs. A set \(D \subseteq V\) is a k-tuple dominating set in G if \(|N[v] \cap D| \geq k\), for all \(v \in V(G)\). The k-tuple domination number, denoted \(\gamma_{\times k}(G)\), is the smallest number of vertices in a k-tuple dominating set. When k = 2, D is called a double dominating set and the 2-tuple domination number is called the double domination number and is denoted by dd(G). In fact the authors showed that every graph G with \(\delta \geq k - 1\) has a k-tuple dominating set and hence a k-tuple domination number.

By a simple uniform approach, we derive many new sharp bounds on \(\alpha_s^2(G)\) in terms of several different graph parameters. Some of our results improve some known bounds on the S2IN of graphs in [8, 11, 12].

The authors noted that most of the existing bounds on \(\alpha_s^2(G)\) are lower bounds. In section 2, we prove that \(\alpha_s^2(G) \geq 2\lfloor \frac{\delta+2\rho(G)}{2} \rfloor - n\), for a graph G of order n. Also in section 3, by a simple connection between the concepts of limited packing and tuple domination, we obtain the exact value of the signed 2-independence numbers of regular graphs. In particular, we bound the signed 2-independence numbers of cubic graphs from below and above just in terms of order as, \(-\frac{n}{3} \leq \alpha_s^2(G) \leq 0\).

2. Main results

At this point we are going to present some sharp upper bounds on \(\alpha_s^2(G)\). First, let us introduce some notation. Let \(f:V\longrightarrow \{-1,1\}\) be a maximum S2IF of G. We define \(V_+=\{v\in V|f(v)=1\}\), \(V_-=\{v\in V|f(v)=-1\}\), \(G_+=G[V_+]\) and \(G_-=G[V_-]\) where \(G_+\) and \(G_-\) are the subgraphs of G induced by \(V_+\) and \(V_-\), respectively. For convenience, let \([V_+,V_-]\) be the set of edges having one end point in \(V_+\) and the other in \(V_-\). Finally, \(deg_{G_+}(v)=|N(v)\cap V_+|\) and \(deg_{G_-}(v)=|N(v)\cap V_-|\). Obviously, \(|V_+|=\frac{n+\alpha_s^2(G)}{2}\) and \(|V_-|=\frac{n-\alpha_s^2(G)}{2}\).

Theorem 2.1. Let G be a graph of order n. Then

\[\alpha_s^2(G) \le \left(\frac{\left\lfloor \frac{\Delta}{2} \right\rfloor - \left\lceil \frac{\delta}{2} \right\rceil + 1}{\left\lfloor \frac{\Delta}{2} \right\rfloor + \left\lceil \frac{\delta}{2} \right\rceil + 1}\right)n\]

and this bound is sharp.

Proof. Let f be a maximum S2IF of G. Let \(v \in V_+\). Since \(f(N[v]) \leq 1\), the vertex v has at least \(\lceil \frac{deg(v)}{2} \rceil \geq \lceil \frac{\delta}{2} \rceil\) neighbors in \(V_-\). Therefore \(|[V_+, V_-]| \geq \lceil \frac{\delta}{2} \rceil |V_+|\). Now let \(v \in V_-\). Since f is a S2IF, the vertex v has at most \(\lfloor \frac{deg(v)}{2} \rfloor + 1 \leq \lfloor \frac{\Delta}{2} \rfloor + 1\) neighbors in \(V_+\). Therefore \(|[V_+, V_-]| \leq (\lfloor \frac{\Delta}{2} \rfloor + 1) |V_-|\). In fact

\[\lceil \frac{\delta}{2} \rceil |V_+| \leq |[V_+, V_-]| \leq (\lfloor \frac{\Delta}{2} \rfloor + 1) |V_-|.\]

Using \(|V_+| = \frac{n + \alpha_s^2(G)}{2}\) and \(|V_-| = \frac{n - \alpha_s^2(G)}{2}\), we obtain the desired upper bound. For sharpness it is sufficient to consider the complete graph \(K_n\).

In [8] the author established a relationship between the signed 2-independence number and the domination number of a graph as follows.

Theorem 2.2. ([8]) If G is a connected graph of order \(n \ge 2\), then \(\alpha_s^2(G) + 2\gamma(G) \le n\), and this bound is sharp.

Now we are going to improve Theorem 2.2. We shall need the following result, which can be found implicit in [4] and explicit in [2] as Corollary 81.

Theorem 2.3. ([2],[4]) If G is a graph with \(\delta \geq k-1\), then \(\gamma_{\times k}(G) \geq \gamma(G) + k-1\).

Theorem 2.4. If G is a connected graph of order n, then \(\alpha_s^2(G) + 2\gamma(G) \le n - 2\lceil \frac{\delta}{2} \rceil + 2\), and this bound is sharp.

Proof. Let f be a maximum S2IF of G. We have shown that \(|N[v] \cap V_-| \geq \lceil \frac{\delta}{2} \rceil\) for all \(v \in V_+\). On the other hand, if \(v \in V_-\), then \(deg_{G_-}(v) \geq \lceil \frac{deg(v)}{2} \rceil - 1 \geq \lceil \frac{\delta}{2} \rceil - 1\). Therefore \(|N[v] \cap V_-| \geq \lceil \frac{\delta}{2} \rceil\). This shows that \(V_-\) is a \(\lceil \frac{\delta}{2} \rceil\)-tuple dominating set in G. This implies, \(|V_-| \geq \gamma_{\times \lceil \frac{\delta}{2} \rceil}(G)\) and hence \(\alpha_s^2(G) \leq n - 2\gamma_{\times \lceil \frac{\delta}{2} \rceil}(G)\). Now by Theorem 2.3, we have \(\alpha_s^2(G) \leq n - 2(\gamma(G) + \lceil \frac{\delta}{2} \rceil - 1)\). Therefore \(\alpha_s^2(G) + 2\gamma(G) \leq n - 2\lceil \frac{\delta}{2} \rceil + 2\). For sharpness it is sufficient to consider the complete graph \(K_n\).

By the concept of limited packing we can present a sharp lower bound on \(\alpha_s^2(G)\) that involves the packing number.

Theorem 2.5. Let G be a connected graph of order n. Then

\[\alpha_s^2(G) \ge 2\lfloor \frac{\delta + 2\rho(G)}{2} \rfloor - n\]

and this bound is sharp.

Proof. Let B be a \(\lfloor \frac{\delta}{2} \rfloor\)-limited packing set in G. Obviously, \(L_{\lfloor \frac{\delta}{2} \rfloor}(G) \leq L_{\lfloor \frac{\delta}{2} + 1 \rfloor}(G)\). We claim that \(B \neq V\). If B = V and \(v \in V\) such that \(deg(v) = \Delta\), then \(\Delta + 1 = |N[v] \cap B| \leq \lfloor \frac{\delta}{2} \rfloor \leq \Delta\), a contradiction. Now let \(u \in V - B\). It is easy to check that \(|N[v] \cap (B \cup \{u\})| \leq \lfloor \frac{\delta}{2} \rfloor + 1\), for all \(v \in V(G)\). Therefore \(B \cup \{u\}\) is a \((\lfloor \frac{\delta}{2} \rfloor + 1)\)-limited packing set in G. Hence

\[L_{\lfloor \frac{\delta}{2} \rfloor + 1}(G) \ge |B \cup \{u\}| = |B| + 1 = L_{\lfloor \frac{\delta}{2} \rfloor}(G) + 1.\]

Repeating these inequalities, we have

\[L_{\lfloor \frac{\delta}{2} \rfloor + 1}(G) \ge L_{\lfloor \frac{\delta}{2} \rfloor}(G) + 1 \ge \dots \ge L_1(G) + \lfloor \frac{\delta}{2} \rfloor = \rho(G) + \lfloor \frac{\delta}{2} \rfloor. \tag{1}\]

Now let B be a maximum (b δ 2 c + 1)-limited packing set in G. We define f : V → {−1, 1} by

\[f(v) = \begin{cases} 1 & \text{if } v \in B \\ -1 & \text{if } v \in V - B. \end{cases}\]

We deduce that

\[\begin{array}{rcl} f(N[v]) & = & |N[v] \cap B| - |N[v] \cap (V - B)| \\ & = & 2|N[v] \cap B| - |N[v]| \le 2\lfloor \frac{\delta}{2} \rfloor - \delta + 1 \le 1, \end{array}\]

for all v ∈ V . Therefore, f is a S2IF of G. This implies

\[\alpha_s^2(G) \ge f(V) = |B| - |V - B| = 2|B| - n = 2L_{\lfloor \frac{\delta}{2} \rfloor + 1}(G) - n.\]

Now (1) implies

\[\alpha_s^2(G) \ge 2L_{\lfloor \frac{\delta}{2} \rfloor + 1}(G) - n \ge 2(\rho(G) + \lfloor \frac{\delta}{2} \rfloor) - n,\]

as desired. Considering the graph Kⁿ we can see that this bound is sharp.

Volkmann in [11] proved that if G is a graph of order n, then 2 − n ≤ α 2 s (G). Moreover if n ≥ 3, then 4 − n ≤ α 2 s (G). Obviously, the lower bound in Theorem 2.5 is an improvement of the first inequality and when δ ≥ 2 this improves the second, as well.

At the end of this section we exhibit a short comment about signed 2-independence number of bipartite graphs. The following upper bound on α 2 s (G) of a bipartite graph was obtained by Wang [12].

Theorem 2.6. ([12]) If G is a bipartite graph of order n ≥ 2, then

\[\alpha_s^2(G) \le n + 6 - 2\sqrt{2n + 9}.\]

Furthermore, the bound is sharp.

We now improve the bound in the previous theorem.

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

\[\alpha_s^2(G) \le n + 2(2 + \lceil \frac{\delta}{2} \rceil) - 2\sqrt{(2 + \lceil \frac{\delta}{2} \rceil)^2 + 2\lceil \frac{\delta}{2} \rceil n}\]

and this bound is sharp.

Proof. Let f be a maximum S2IF of G. Let X and Y be the partite sets of G. For convenience we define X⁺ = X ∩ V ⁺, X⁻ = X ∩ V ⁻ and let Y ⁺ and Y ⁻ be defined, analogously. Obviously, V ⁺ = X⁺ ∪ Y ⁺ and V ⁻ = X⁻ ∪ Y ⁻.

Since every vertex in X⁺ has at least d δ 2 e neighbors in Y ⁻, by the pigeonhole principle, there exists a vertex v in Y ⁻ that is joined to at least ^d 2 e|X+| |Y ⁻| vertices in X+. This implies

\[\frac{\lceil \frac{\delta}{2} \rceil |X_+|}{|Y_-|} - |X_-| - 1 \leq |N[v] \cap X_+| - |N[v] \cap X_-| - 1 = f(N[v]) \leq 1,\]

and hence

\[\lceil \frac{\delta}{2} \rceil |X_+| \le |Y_-|(|X_-| + 2).\] (2)

A similar argument shows that

\[\lceil \frac{\delta}{2} \rceil |Y_+| \le |X_-|(|Y_-| + 2).\] (3)

Using inequalities (2) and (3) we have

\[\lceil \frac{\delta}{2} \rceil |V_+| \leq 2|X_-||Y_-| + 2|V_-| \leq \frac{1}{2} (|X_-| + |Y_-|)^2 + 2|V_-| = \frac{1}{2} |V_-|^2 + 2|V_-|.\]

Using |V ⁺| = n − |V ⁻|, we obtain

\[|V_{-}|^{2} + (4 + 2\lceil \frac{\delta}{2} \rceil)|V_{-}| - 2|V_{-}|n \ge 0.\]

This yields to |V ⁻| ≥ ⁻4−2^d 2 e+ √ (4+2d e) ²+8d en 2 . Now, by using the value of |V ⁻| we derive the desired bound.

Using calculus we can see that g(x) = n + 2(x + 2) − 2 p (x + 2)² + 2nx is a decreasing function for x ≥ 0. So, for δ ≥ 1, d δ 2 e ≥ 1 implies that

\[n + 2(2 + \lceil \frac{\delta}{2} \rceil) - 2\sqrt{(2 + \lceil \frac{\delta}{2} \rceil)^2 + 2\lceil \frac{\delta}{2} \rceil n} \le n + 6 - 2\sqrt{2n + 9}\]

and therefore Theorem 2.7 is an improvement of Theorem 2.6.

3. Remarks on signed 2-independence in regular graphs

Zelinka [14] obtained the following sharp upper bound on α 2 s (G) for regular graphs G.

Theorem 3.1. ([14]) If G is an r-regular graph of order n, then α 2 s (G) ≤ n ^r+1 when r is even and α 2 s (G) ≤ 0 when r is odd.

We note that the bound in Theorem 2.1 implies the previous result. The authors in [9] proved the following result.

Lemma 3.1. ([9]) Let G be a graph. Then the following statements hold.

• (i) Let \(\delta \geq k-1\). If \(B \subseteq V\) is a k-limited packing set, then V-B is a \((\delta-k+1)\) tuple dominating set in G.
• (ii) Let \(\delta \geq k\). If \(D \subseteq V\) is a k-tuple dominating set, then V D is a \((\Delta k + 1)\)-limited packing set in G.

Now, by the above lemma we are able to obtain the exact value of the signed 2-independence number of regular graphs, first in terms of order and limited packing number, second in terms of order and tuple domination number. At the end we bound \(\alpha_s^2(G)\) of a cubic graph G from above and below, just in terms of the order. First we need the following lemma.

Lemma 3.2. Let G be a graph of order n, then

(i) \[2L_{|\frac{\delta}{2}|+1}(G) - n \le \alpha_s^2(G) \le 2L_{|\frac{\Delta}{2}|+1}(G) - n\]

\[(ii) \ n - 2\gamma_{\times \lceil \frac{\Delta}{2} \rceil}(G) \le \alpha_s^2(G) \le n - 2\gamma_{\times \lceil \frac{\delta}{2} \rceil}(G).\]

Proof. (i) In the proof of Theorem 2.5 we have seen that \(2L_{\lfloor \frac{\delta}{2} \rfloor+1}(G)-n \leq \alpha_s^2(G)\).

Now let f be a maximum S2IF of G. In the proof of Theorem 2.1 we have shown that \(|N[v] \cap V_+| \leq \lfloor \frac{\Delta}{2} \rfloor + 1\), for all \(v \in V_-\). On the other hand, if \(v \in V_+\), then \(deg_{G_+}(v) \leq \lfloor \frac{deg(v)}{2} \rfloor \leq \lfloor \frac{\Delta}{2} \rfloor\). Therefore \(V_+\) is a \((\lfloor \frac{\Delta}{2} \rfloor + 1)\)-limited packing set in G. This implies \(|V_+| \leq L_{\lfloor \frac{\Delta}{2} \rfloor + 1}(G)\) and hence \(\alpha_s^2(G) \leq 2L_{\lfloor \frac{\Delta}{2} \rfloor + 1}(G) - n\).

(ii) According to the proof of Theorem 2.4, we have \(\alpha_s^2(G) \leq n - 2\gamma_{\times \lceil \frac{\delta}{\alpha} \rceil}(G)\).

Now let D be a minimum \(\lceil \frac{\Delta}{2} \rceil\)-tuple dominating set in G. We define \(f: V \to \{-1, 1\}\) by

\[f(v) = \begin{cases} -1 & \text{if } v \in D \\ 1 & \text{if } v \in V - D. \end{cases}\]

By the previous lemma, we conclude that \(f(N[v]) = |N[v] \cap (V-D)| - |N[v] \cap D| \le \Delta - \lceil \frac{\Delta}{2} \rceil + 1 - \lceil \frac{\Delta}{2} \rceil \le 1\). Therefore f is a S2IF of G. This implies \(\alpha_s^2(G) \ge f(V) = |V-D| - |D| = n - 2|D| = n - 2\gamma_{\times \lceil \frac{\Delta}{2} \rceil}(G)\).

Considering regular graphs, by the previous lemma, we have the following corollary.

Corollary 3.1. Let G be an r-regular graph of order n. Then

(i) \[\alpha_s^2(G) = 2L_{\lfloor \frac{r}{2} \rfloor + 1}(G) - n\].

(ii) \[\alpha_s^2(G) = n - 2\gamma_{\times \lceil \frac{r}{2} \rceil}(G)\].

As an immediate result of the previous corollary we obtain the following.

Corollary 3.2. If G is a cubic graph of order n, then

(i) \[\alpha_s^2(G) = 2L_2(G) - n\].

(ii) \[\alpha_s^2(G) = n - 2dd(G)\].

In [1], the authors showed that if G is a cubic graph of order n, then \(\frac{n}{3} \leq L_2(G)\). Moreover, the upper bound \(L_2(G) \leq \frac{n}{2}\) was presented in [5] for a cubic graph G. Therefore Corollary 3.2 leads to

\[-\tfrac{n}{3} \leq \alpha_s^2(G) \leq 0\]

for cubic graphs.

Acknowledgement

The authors are grateful to the referee for his/her valuable suggestions.

References

• [1] P.N. Balister, B. Bollobas and K. Gunderson, Limited packings of closed neighbourhoods in graphs, arXiv: 1501.01833v1 [math.CO] 8 Jan 2015.
• [2] M. Chellali, O. Favaron, A. Hansberg and L. Volkmann, k-Domination and k-independence in graphs, Graphs Combin. 28 (2012) 1–55.
• [3] W. Chen and E. Song, Lower bounds on several versions of signed domination number, Discrete Math. 308 (2008) 1837–1846.
• [4] O. Favaron, M.A. Henning, J. Puech and D. Rautenbach, On domination and annihilation in graphs with claw-free blocks, Discrete Math. 231 (2001) 143–151.
• [5] R. Gallant, G. Gunther, B.L. Hartnell and D.F. Rall, Limited packing in graphs, Discrete Appl. Math. 158 (2010) 1357–1364.
• [6] F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201–213.
• [7] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs, New York, Marcel Dekker, 1998.
• [8] M.A. Henning, Signed 2-independence in graphs, Discrete Math. 250 (2002) 93–107.
• [9] D.A. Mojdeh, B. Samadi and S.M. Hosseini Moghaddam, Limited packing vs tuple domination in graphs, Ars Combin., to appear.
• [10] E.F. Shan, M.Y. Sohn and L.Y. Kang, Upper bounds on signed 2-independence numbers of graphs, Ars Combin. 69 (2003) 229–239.
• [11] L. Volkmann, Bounds on the signed 2-independence number in graphs, Discuss. Math. Graph Theory 33 (2013) 709–715.
• [12] C. Wang, The modified negative decision number in graphs, Internat. J. Math. Math. Sci. Volume 2011 (2011), Article ID 135481, 9 pages.
• [13] D.B. West, Introduction to Graph Theory (Second Edition), Prentice Hall, USA, 2001.
• [14] B. Zelinka, On signed 2-independence number of graphs, manuscript.