Signed 2-independence in graphs (Q1613437)

For a vertex \(v\) of a graph \(G=(V,E)\), its closed neighbourhood \(N[v]\) consists of \(v\) and all adjacent vertices. \(f:V\to\{-1,+1\}\) is a signed 2-independence function if the sum of its values over all points in any \(N[v]\) does not exceed 1. The weight of \(f\) is \(\sum\limits_{v\in V} f(v)\). A set \(S\) of vertices is a 2-packing if distinct vertices in \(S\) have disjoint closed neighbourhoods. The author investigates the signed 2-independence number of \(G\), \(\alpha_s^2(G)\),---introduced in a recent manuscript of B. Zelinka---defined to be the maximum weight of a signed 2-independence function. For integer \(m\geq 1\), let \({\mathcal G}_m\) be the family of graphs of order \((m+2)m\) obtained from the disjoint union of \(m\) stars \(K_{1,m+1}\) by adding (1) all possible edges between the central vertices to create a \(K_m\), and (2) possibly, edges between the \((m+1)m\) end-vertices so that each is joined to at most one other end-vertex; \({\mathcal G}_m^\prime\) is the subfamily of \({\mathcal G}_m\) in which the end-vertices induce a perfect matching. \[ {\mathcal G}=\bigcup_{m=1}^\infty{\mathcal G}_m; \qquad {\mathcal G^\prime}=\bigcup_{m=1}^\infty{\mathcal G}_m^\prime. \] Let \(G=(V,E)\) be a graph with \(n=|V|\) and \(q=|E|\). Theorem 3. If \(G\) is connected and \(n\geq 2\), then \(\alpha^2_s(G)\leq n+2-2\sqrt{n+1}\), with equality iff \(G\in{\mathcal G}\). Theorem 4. If \(G\) is connected, with minimum degree \(\delta(G)\geq 2\), then \(\alpha^2_s(G)\leq n+2-2\sqrt{n+1}\), with equality if and only if \(G\in{\mathcal G}^\prime\). Theorem 6. Let the vertices of \(G\) be so labelled that their degrees satisfy \(d_{i-1}\leq d_i\) \((i=1,2,\dots,n)\). If \(k\) is the largest integer for which \(\sum\limits_{i=1}^kd_i-\sum\limits_{j=k+1}^nd_i\leq 2(n-k)\), then \(\alpha_s^2(G)\leq 2k-n\). Theorem 7. If \(G\) is connected, \(n\geq 2\), and \(\gamma(G)\) denotes the domination number -- the minimum cardinality of a set \(S\) of vertices such that every vertex not in \(S\) is adjacent to a vertex in \(S\), then \(\alpha_s^2(G)+2\gamma(G)\leq n\), and this bound is sharp. In Theorem 5 it is shown that, for connected \(G\), \(\alpha^2_s(G)\leq\frac{4q-n}5\), and the cases of equality are characterized; in Corollary 8 this is applied to trees \(T\) of order \(n\geq 2\), to conclude that \(\alpha_s^2(T)\leq\frac{3n-4}5\), and the cases of equality are again characterized. Theorems 10, 12. For any tree \(T\), \(\alpha_s^2(T)\geq 0\), with equality holding iff \(T\) has a 2-packing which dominates \(T\), and in which every vertex has odd degree. Finally, Theorem 13 proves that the 2-independence numbers of cubic graphs can be arbitrarily large negatively.