On the \(k\)-component independence number of a tree (Q2045314)

Summary: Let \(G\) be a graph and \(k\geq1\) be an integer. A subset \(S\) of vertices in a graph \(G\) is called a \(k\)-component independent set of \(G\) if each component of \(G[S]\) has order at most \(k\). The \(k\)-component independence number, denoted by \(\alpha_c^k(G)\), is the maximum order of a vertex subset that induces a subgraph with maximum component order at most \(k\). We prove that if a tree \(T\) is of order \(n\), then \(\alpha_k(T)\geq(k/(k+1))n\). The bound is sharp. In addition, we give a linear-time algorithm for finding a maximum \(k\)-component independent set of a tree.