On the minimum number of maximal distance-$k$ independent sets in trees
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913075843563520 |
|---|---|
| author | Taletskii, Dmitrii |
| author_facet | Taletskii, Dmitrii |
| contents | A vertex subset of a graph is called a distance-$k$ independent set if the distance between any two of its distinct vertices is at least $k + 1$. For all $n,k \geq 1$, we determine the minimum possible number of inclusion-wise maximal distance-$k$ independent sets among all $n$-vertex trees. It equals $n$ if $n \leq k + 1$, and $n - \bigg\lfloor \frac{n - (k \bmod 2)}{\lfloor k/2 \rfloor + 1} \bigg\rfloor + 1$ otherwise. We also completely describe the class of trees attaining this bound and determine the growth rate of the number of such $n$-vertex trees for a fixed $k \geq 1$. If $k$ is odd and $(k+1)/2$ does not divide $n-1$, then the number of non-isomorphic $n$-vertex trees with the minimum possible number of maximal distance-$k$ independent sets grows linearly with $n$. Otherwise, it is bounded above by the number of unlabeled $k^2$-vertex trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_27424 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the minimum number of maximal distance-$k$ independent sets in trees Taletskii, Dmitrii Combinatorics 05C30 A vertex subset of a graph is called a distance-$k$ independent set if the distance between any two of its distinct vertices is at least $k + 1$. For all $n,k \geq 1$, we determine the minimum possible number of inclusion-wise maximal distance-$k$ independent sets among all $n$-vertex trees. It equals $n$ if $n \leq k + 1$, and $n - \bigg\lfloor \frac{n - (k \bmod 2)}{\lfloor k/2 \rfloor + 1} \bigg\rfloor + 1$ otherwise. We also completely describe the class of trees attaining this bound and determine the growth rate of the number of such $n$-vertex trees for a fixed $k \geq 1$. If $k$ is odd and $(k+1)/2$ does not divide $n-1$, then the number of non-isomorphic $n$-vertex trees with the minimum possible number of maximal distance-$k$ independent sets grows linearly with $n$. Otherwise, it is bounded above by the number of unlabeled $k^2$-vertex trees. |
| title | On the minimum number of maximal distance-$k$ independent sets in trees |
| topic | Combinatorics 05C30 |
| url | https://arxiv.org/abs/2604.27424 |