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!
|
| _version_ | 1866916150535782400 |
|---|---|
| author | Bruyère, Véronique Joret, Gwenaël Mélot, Hadrien |
| author_facet | Bruyère, Véronique Joret, Gwenaël Mélot, Hadrien |
| 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1002_1270 |
| institution | arXiv |
| publishDate | 2010 |
| record_format | arxiv |
| spellingShingle | Trees with Given Stability Number and Minimum Number of Stable Sets Bruyère, Véronique Joret, Gwenaël Mélot, Hadrien Combinatorics 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. |
| title | Trees with Given Stability Number and Minimum Number of Stable Sets |
| topic | Combinatorics |
| url | https://arxiv.org/abs/1002.1270 |