Trees with Given Stability Number and Minimum Number of Stable Sets

Bruyère, Véronique; Joret, Gwenaël; Mélot, Hadrien

No full text

Article (Scientific journals)

Trees with Given Stability Number and Minimum Number of Stable Sets

Bruyère, Véronique; Joret, Gwenaël; Mélot, Hadrien

2012 • In Graphs and Combinatorics, 28 (2), p. 167-187

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/20.500.12907/29635

Files (2)Send to Details Statistics Bibliography Similar publications

Files

Full Text

No document available.

Annexes

GraphComb_onlineFirst_2011.pdf

Publisher postprint (477.14 kB)

Request a copy

AsPublished.pdf

Publisher postprint (455.57 kB)

Request a copy

All documents in ORBi UMONS are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

[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

Publication date :

01 March 2012

Journal title :

Graphs and Combinatorics

ISSN :

0911-0119

Publisher :

Springer, Germany

Volume :

Issue :

Pages :

167-187

Peer reviewed :

Peer Reviewed verified by ORBi

Research unit :

S829 - Informatique théorique
S825 - Algorithmique

Research institute :

R300 - Institut de Recherche en Technologies de l'Information et Sciences de l'Informatique
R150 - Institut de Recherche sur les Systèmes Complexes

Commentary :

DOI: 10.1007/s00373-011-1041-2

Available on ORBi UMONS :

since 31 January 2012

Statistics

Number of views

14 (0 by UMONS)

Number of downloads

0 (0 by UMONS)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

Bibliography

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).