×

A note on signed total 2-independence in graphs. (English) Zbl 1238.05205

For any vertex \(v\) of a graph \(G\), \(N(v)\) denotes the set of vertices adjacent to \(v\). A signed total 2-independence function \(f:V(G)\to\{-1,+1\}\) on a graph \(G\) without isolated vertices satisfies \(\sum\limits_{u\in N(v)}f(u)\geq1\) for all \(v\in V(G)\). The weight \(w(f)\) of such a function is \(\sum_{v\in V(G)}f(v)\); the maximum weight over all signed total 2-independence functions on \(G\) is the signed total 2-independence number \(\alpha^2_{st}(G)\); \(\alpha^2_{st}\) is called the negative decision number in [C. Wang, “The negative decision number in graphs”, Australas. J. Comb. 41, 263–272 (2008; Zbl 1154.05050)]. From the authors’ introduction: “In this paper we continue the study on \(\alpha^2_{st}(G)\), and present some sharp boundsfor general graphs and \(K_{r+1}\)-free graphs. Some known bounds on \(\alpha^2_{st}(G)\) are improved or extended.”

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C22 Signed and weighted graphs
05C35 Extremal problems in graph theory

Citations:

Zbl 1154.05050
PDFBibTeX XMLCite