Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.11857 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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 \neq 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\le 5$, apart from one exception every tree with $n\neq k$ contains $k+1$ disjoint independent all-$k$-isolating sets.