Trees with Given Stability Number and Minimum Number of Stable Sets

摘要

We study the structure of trees minimizing their number of stable sets for given order n and stability number α. Our main result is that the edges of a non-trivial extremal tree can be partitioned into n − α stars, each of size ${lceilfrac{n-1}{n-alpha}rceil}$ or ${lfloorfrac{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.