All-$k$-Isolation in Trees
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915495190462464 |
|---|---|
| author | Boyer, Geoffrey Farrell, Garrett C. Goddard, Wayne |
| author_facet | Boyer, Geoffrey Farrell, Garrett C. Goddard, Wayne |
| 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_11857 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | All-$k$-Isolation in Trees Boyer, Geoffrey Farrell, Garrett C. Goddard, Wayne Combinatorics 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. |
| title | All-$k$-Isolation in Trees |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.11857 |