New results on \(k\)-independence of graphs (Q528993)

Summary: Let \(G = (V, E)\) be a graph and \(k \geq 0\) an integer. A \(k\)-independent set~\(S \subseteq G\) is a set of vertices such that the maximum degree in the graph induced by \(S\) is at most \(k\). Denote by \(\alpha_{k}(G)\) the maximum cardinality of a \(k\)-independent set of \(G\). For a graph \(G\) on \(n\) vertices and average degree \(d\), Turán's theorem asserts that \(\alpha_{0}(G) \geq \frac{n}{d+1}\), where the equality holds if and only if \(G\) is a union of cliques of equal size. For general \(k\) we prove that \(\alpha_{k}(G) \geq \dfrac{(k+1)n}{d+k+1}\), improving on the previous best bound \(\alpha_{k}(G) \geq \dfrac{(k+1)n}{ \lceil d \rceil+k+1}\) of \textit{Y. Caro} and \textit{A. Hansberg} [Electron. J. Comb. 20, No. 1, Research Paper P33, 17 p. (2013; Zbl 1266.05110)]. For \(1\)-independence we prove that equality holds if and only if \(G\) is either an independent set or a union of almost-cliques of equal size (an almost-clique is a clique on an even number of vertices minus a \(1\)-factor). For \(2\)-independence, we prove that equality holds~if and only if \(G\) is an independent set. Furthermore when \(d>0\) is an integer divisible by 3 we prove that \(\alpha_2(G) \geq \dfrac{3n}{d+3} \left( 1 + \dfrac{12}{5d^2 + 25d + 18} \right)\).