Fibonacci index and stability number of graphs: a polyhedral study

DOI10.1007/s10878-009-9228-7zbMath1203.05074arXiv0811.1449OpenAlexW1633290649MaRDI QIDQ1041432

Hadrien Mélot, Véronique Bruyère

Publication date: 2 December 2009

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0811.1449

zbMATH Keywords

stable setMerrifield-Simmons indexTuran graphGraPHedron\(\alpha \)-critical graphFibonacci index

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Applications of graph theory (05C90) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Maxima and minima of the Hosoya index and the Merrifield-Simmons index ⋮ Trees with given stability number and minimum number of stable sets ⋮ Maximizing the number of independent sets of fixed size in connected graphs with given independence number ⋮ Graphs with few total dominating sets ⋮ Graphs with given number of cut vertices and extremal Merrifield-Simmons index ⋮ Graphs with maximal Hosoya index and minimal Merrifield-Simmons index

Uses Software

• GraPHedron

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enumerating maximal independent sets with applications to graph colouring.
• Unicycle graphs with extremal Merrifield-Simmons index
• The first and second largest Merrifield-Simmons indices of trees with prescribed pendent vertices
• Facet defining inequalities among graph invariants: The system graphedron
• Another extremal problem for Turan graphs
• Graphs, partitions and Fibonacci numbers
• Bounds on the number of vertex independent sets in a graph
• The number of independent sets in unicyclic graphs
• Linear inequalities among graph invariants: Using GraPHedron to uncover optimal relationships
• Turán's theorem and k‐connected graphs
• Maximizing the number of independent subsets over trees with bounded degree
• Turán Graphs, Stability Number, and Fibonacci Index