Trees with Given Stability Number and Minimum Number of Stable Sets

Abstract

We study the structure of trees minimizing their number of stable sets for given order $n$ and stability number $\alpha$. Our main result is that the edges of a non-trivial extremal tree can be partitioned into $n-\alpha$ stars, each of size $\lceil \frac{n-1}{n-\alpha }\rceil$ or $\lfloor \frac{n-1}{n-\alpha }\rfloor$, so that every vertex is included in at most two distinct stars, and the centers of these stars form a stable set of the tree.

v2: Referees' comments incorporated

References in corpus (1)

• Fibonacci Index and Stability Number of Graphs: a Polyhedral Study