Paper Info
Title
Fibonacci index and stability number of graphs: a polyhedral study
Abstract
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 .
Year
DOI
Venue
2009
https://doi.org/10.1007/s10878-009-9228-7
Journal of Combinatorial Optimization
Keywords
DocType
Volume
Stable set,Fibonacci index,Merrifield-Simmons index,Turán graph,α,-critical graph,GraPHedron
Journal
18
Issue
ISSN
Citations 
SP3
1382-6905
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Véronique Bruyère142943.59
Hadrien Melot29514.02