On \(k\)-independence in graphs with emphasis on trees (Q2643314): Difference between revisions

This article studies \(k\)-independence in graphs, which is defined as the property that any subgraph induced by a subset of the vertices has maximum degree at most \(k-1\). The authors begin by a section containing useful definitions and background information, and then proceed to the main contribution of this article, which is a number of bounds on the lower \(k\)-independence number and the \(k\)-independence number. Different bounds are presented for connected graphs, connected bipartite graphs and trees. The last section contains a complete characterization of the trees where the bounds are attained with equality.