On kk-independence in graphs with emphasis on trees

In a graph G=(V,E)G=(V,E) of order nn and maximum degree ΔΔ, a subset SS of vertices is a kk-independent set if the subgraph induced by SS has maximum degree less or equal to k-1k-1. The lower kk-independence number ikik(G)(G) is the minimum cardinality of a maximal kk-independent set in GG and the kk-independence number βk(G)βk(G) is the maximum cardinality of a kk-independent set. We show that ik⩽n-Δ+k-1ik⩽n-Δ+k-1 for any graph and any k⩽Δk⩽Δ, and i2⩽n-Δi2⩽n-Δ if GG is connected, that βk(T)⩾kn/(k+1)βk(T)⩾kn/(k+1) for any tree, and that i2⩽(n+s)/2⩽β2i2⩽(n+s)/2⩽β2 for any connected bipartite graph with ss support vertices. Moreover, we characterize the trees satisfying i2=n-Δi2=n-Δ, βk=kn/(k+1)βk=kn/(k+1), i2=(n+s)/2i2=(n+s)/2 or β2=(n+s)/2β2=(n+s)/2.