[en] Merrifield-Simmons index; [en] Stability number; [en] Fibonacci number
Abstract :
[en] We study the structure of trees minimizing their number of stable sets for given order n and stability number a. Our main result is that the edges of a non-trivial extremal tree can be partitioned into n - a stars 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.
Research center :
CREMMI - Modélisation mathématique et informatique
Disciplines :
Electrical & electronics engineering Mathematics
Author, co-author :
Bruyère, Véronique ; Université de Mons > Faculté des Sciences > Service d'Informatique théorique
Joret, Gwenaël
Mélot, Hadrien ; Université de Mons > Faculté des Sciences > Algorithmique
Language :
English
Title :
Trees with Given Stability Number and Minimum Number of Stable Sets
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).
