[en] The Fibonacci index of a graph is the number of its stable sets. This parameter is widely studied and has applications in chemical graph theory. In this paper, we establish tight upper bounds for the Fibonacci index in terms of the stability number and the order of general graphs and connected graphs. Turán graphs frequently appear in extremal graph theory. We show that Turán graphs and a connected variant of them are also extremal for these particular problems. We also make a polyhedral study by establishing all the optimal linear inequalities for the stability number and the Fibonacci index, inside the classes of general and connected graphs of order n.
Berge C (2001) The theory of graphs. Dover, New York
N Bougard G Joret 2008 Turán Theorem and k-connected graphs J Graph Theory 58 1 13 1145.05026 10.1002/jgt.20289 2404037 (Pubitemid 351661168)
R-L Brooks 1941 On colouring the nodes of a network Proc Camb Philos Soc 37 194 197 10.1017/S030500410002168X 12236
Bruyère V, Mélot H (2008) Turàn graphs, stability number, and Fibonacci index. In: Combinatorial Optimization and Applications, COCOA 2008, St. John's, Newfoundland, Canada, 2008. Lecture Notes in Computer Science, vol 5165. Springer, Berlin, pp 127-138
JM Byskov 2004 Enumerating maximal independent sets with applications to graph colouring Oper Res Lett 32 547 556 1052.05055 10.1016/j.orl.2004.03.002 2077457
J Christophe S Dewez J-P Doignon S Elloumi G Fasbender P Grégoire D Huygens M Labbé H Mélot H Yaman 2008 Linear inequalities among graph invariants: using GraPHedron to uncover optimal relationships Networks 52 287 298 1151.05334 10.1002/net.20250 2474619
P Erdös T Gallai 1961 On the minimal number of vertices representing the edges of a graph M Tud Akad Mat Kut Intéz Közl 6 181 203 0101.41001
Foulds LR (1992) Graph theory applications. Springer, New York
GraPHedron (2009) Reports on the study of the Fibonacci index and the stability number of graphs and connected graphs. URL: www.graphedron.net/index. php?page=viewBib&bib=10
Gutman I, Polansky OE (1986) Mathematical concepts in organic chemistry. Springer, Berlin
B Hedman 1987 Another extremal problem for Turán graphs Discrete Math 65 173 176 0629.05041 10.1016/0012-365X(87)90139-7 893078
C Heuberger S Wagner 2008 Maximizing the number of independent subsets over trees with bounded degree J Graph Theory 58 49 68 1156.05042 10.1002/jgt.20294 2404041 (Pubitemid 351661172)
Joret G (2007) Entropy and stability in graphs. PhD thesis, Université Libre de Bruxelles, Belgium
A Knopfmacher RF Tichy S Wagner V Ziegler 2007 Graphs, partitions and Fibonacci numbers Discrete Appl Math 155 1175 1187 1121.05031 10.1016/j.dam.2006.10.010 2332311 (Pubitemid 46602564)
X Li Z Li L Wang 2003 The Inverse Problems for Some Topological Indices in Combinatorial Chemistry J Comput Biol 10 1 47 55 10.1089/106652703763255660 (Pubitemid 36315622)
X Li H Zhao I Gutman 2005 On the Merrifield-Simmons Index of Trees MATCH Commun Math Comput Chem 54 389 402 1084.05018 2201592
Lovász L (1993) Combinatorial problems and exercises, 2nd edn. North-Holland, Amsterdam
Lovász L, Plummer MD (1986) Matching Theory. Akadémiai Kiadó-North-Holland, Budapest
H Mélot 2008 Facet defining inequalities among graph invariants: the system GraPHedron Discrete Appl Math 156 1875 1891 1152.05380 10.1016/j.dam.2007.09.005 2432949
Merrifield RE, Simmons HE (1989) Topological methods in chemistry. Wiley, New York
AS Pedersen PD Vestergaard 2005 The number of independent sets in unicyclic graphs Discrete Appl Math 152 246 256 1080.05069 10.1016/j.dam.2005. 04.002 2174205 (Pubitemid 41427509)
AS Pedersen PD Vestergaard 2006 Bounds on the number of vertex independent sets in a graph Taiwan J Math 10 6 1575 1587 1123.05068 2275147
AS Pedersen PD Vestergaard 2007 An upper bound on the number of independent sets in a tree Ars Comb 84 85 96 2332890
H Prodinger RF Tichy 1982 Fibonacci numbers of graphs Fibonacci Q 20 1 16 21 0475.05046 660753
RF Tichy S Wagner 2005 Extremal problems for topological indices in combinatorial chemistry J Comput Biol 12 7 1004 1013 10.1089/cmb.2005.12.1004 (Pubitemid 41384394)
P Turán 1941 Eine Extremalaufgabe aus der Graphentheorie Mat Fiz Lapok 48 436 452 0026.26903 18405
S Wagner 2007 Extremal trees with respect to Hosoya Index and Merrifield-Simmons Index MATCH Commun Math Comput Chem 57 221 233 1150.05034 2293907
H Wang H Hua 2008 Unicycle graphs with extremal Merrifield-Simmons Index J Math Chem 43 1 202 209 1143.05061 10.1007/s10910-006-9188-4 2449414
M Wang H Hua D Wang 2008 The first and second largest Merrifield-Simmons indices of trees with prescribed pendent vertices J Math Chem 43 2 727 736 05312615 10.1007/s10910-006-9224-4 2433467
