All-k-Isolation in Trees

We define an all-k-isolating set of a graph to be a set S of vertices such that, if one removes S and all its neighbors, then no component in what remains has order k or more. The case $k=1$ corresponds to a dominating set and the case $k=2$ corresponds to what Caro and Hansberg called an isolating set. We show that every tree of order n ≠ k contains an all-k-isolating set S of size at most $n/(k+1)$, and moreover, the set S can be chosen to be an independent set. This extends previous bounds on variations of isolation, while improving a result of Luttrell et al., who called the associated parameter the k-neighbor component order connectivity. We also characterize the trees where this bound is achieved. Further, we show that for~k≤ 5, apart from one exception every tree with n≠ k contains $k+1$ disjoint independent all-k-isolating sets.