On the minimum number of maximal distance-$k$ independent sets in trees

Abstract

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\ge 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\le k+1$, and $n-\lfloor \frac{n-(k\mathrm{mod}2)}{\lfloor k/2\rfloor +1}\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\ge 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.

19 pages, 4 figures