Trees with Given Stability Number and Minimum Number of Stable Sets

Details Trees with Given Stability Number and Minimum Number of Stable Sets Trees with Given Stability Number and Minimum Number of Stable Sets

2010-02-05

arxiv.org/abs/1002.1270v2

Mathematics

Combinatorics

v2: Referees' comments incorporated

Scientific paper

10.1007/s00373-011-1041-2

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.

Affiliated with

Also associated with

No associations

Rating

Trees with Given Stability Number and Minimum Number of Stable Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Trees with Given Stability Number and Minimum Number of Stable Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Trees with Given Stability Number and Minimum Number of Stable Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-536063