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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alameddine A.F.: Bounds on the Fibonacci number of a maximal outerplanar graph. Fibonacci Q. 36(3), 206–210 (1998)
Bruyère V., Mélot H.: Fibonacci index and stability number of graphs: a polyhedral study. J. Combin. Optim. 18, 207–228 (2009)
Deng H., Chen S., Zhang J.: The Merrifield–Simmons index in (n, n + 1)-graphs. J. Math. Chem. 43(1), 75–91 (2008)
Diestel R.: Graph theory. Graduate Texts in Mathematics, vol. 173, 3rd edn. Springer, Berlin (2005)
Gutman I., Polansky O.E.: Mathematical Concepts in Organic Chemistry. Springer, Berlin (1986)
Heuberger C., Wagner S.: Maximizing the number of independent subsets over trees with bounded degree. J. Graph Theory 58, 49–68 (2008)
Kahn J.: An entropy approach to the hard-core model on bipartite graphs. Combin. Probab. Comput. 10(3), 219–237 (2001)
Knopfmacher A., Tichy R.F., Wagner S., Ziegler V.: Graphs, partitions and Fibonacci numbers. Discrete Appl. Math. 155, 1175–1187 (2007)
Li S., Li X., Jing W.: On the extremal Merrifield–Simmons index and Hosoya index of quasi-tree graphs. Discrete Appl. Math. 157(13), 2877–2885 (2009)
Li S., Zhu Z.: The number of independent sets in unicyclic graphs with a given diameter. Discrete Appl. Math. 157(7), 1387–1395 (2009)
Li X., Zhao H., Gutman I.: On the Merrifield–Simmons index of trees. MATCH Commun. Math. Comp. Chem. 54, 389–402 (2005)
Lin S.B., Lin C.: Trees and forests with large and small independent indices. Chin. J. Math. 23(3), 199–210 (1995)
Mélot H.: Facet defining inequalities among graph invariants: the system GraPHedron. Discrete Appl. Math. 156, 1875–1891 (2008)
Merrifield R.E., Simmons H.E.: Topological Methods in Chemistry. Wiley, New York (1989)
Pedersen A.S., Vestergaard P.D.: The number of independent sets in unicyclic graphs. Discrete Appl. Math. 152, 246–256 (2005)
Pedersen A.S., Vestergaard P.D.: Bounds on the number of vertex independent sets in a graph. Taiwanese J. Math. 10(6), 1575–1587 (2006)
Pedersen A.S., Vestergaard P.D.: An upper bound on the number of independent sets in a tree. Ars Combin. 84, 85–96 (2007)
Prodinger H., Tichy R.F.: Fibonacci numbers of graphs. Fibonacci Q. 20(1), 16–21 (1982)
Wang H., Hua H.: Unicycle graphs with extremal Merrifield–Simmons Index. J. Math. Chem. 43(1), 202–209 (2008)
Wang M., Hua H., Wang D.: The first and second largest Merrifield–Simmons indices of trees with prescribed pendent vertices. J. Math. Chem. 43(2), 727–736 (2008)
Yu A., Lv X.: The Merrifield–Simmons indices and Hosoya indices of trees with k pendant vertices. J. Math. Chem. 41(1), 33–43 (2007)
Zhu Z., Li S., Tan L.: Tricyclic graphs with maximum Merrifield–Simmons index. Discrete Appl. Math. 158(3), 204–212 (2010)
Author information
Authors and Affiliations
Corresponding author
Additional information
G. Joret is a Postdoctoral Researcher of the Fonds National de la Recherche Scientifique (F.R.S.–FNRS).
Rights and permissions
About this article
Cite this article
Bruyère, V., Joret, G. & Mélot, H. Trees with Given Stability Number and Minimum Number of Stable Sets. Graphs and Combinatorics 28, 167–187 (2012). https://doi.org/10.1007/s00373-011-1041-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-011-1041-2