Abstract | ||
---|---|---|
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-\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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/s00373-011-1041-2 | Graphs and Combinatorics |
Keywords | Field | DocType |
main result,order n,stability number · fibonacci number · merrifield-simmons index,stability number,non-trivial extremal tree,distinct star,stable sets,stable set,minimum number,fibonacci number,indexation | Discrete mathematics,Topology,Combinatorics,Vertex (geometry),Stars,Independent set,Mathematics,Fibonacci number | Journal |
Volume | Issue | ISSN |
28 | 2 | 1435-5914 |
Citations | PageRank | References |
1 | 0.37 | 9 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Véronique Bruyère | 1 | 429 | 43.59 |
Gwenaël Joret | 2 | 196 | 28.64 |
Hadrien Melot | 3 | 95 | 14.02 |