On the minimum number of maximal distance-$k$ independent sets in trees
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.27424
curl -X POST /api/v1/records/arxiv/2604.27424/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.27424/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'