Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2010
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1002.1270 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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 $\lceil \frac{n-1}{n-α} \rceil$ or $\lfloor \frac{n-1}{n-α}\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.