An extension of the Chvátal-Erdős theorem: counting the number of maximum independent sets

DOI10.1007/S00373-014-1416-2MaRDI QIDQ2354602zbMATH OpenOpenAlexFDO

Authors Haicheng Ma, Tingzeng Wu, Guantao Chen, Yinkui Li, Liming Xiong

Publication date 20 July 2015

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-014-1416-2

zbMATH Keywords

Chvátal-Erdős theoremconnectivityindependence numbermaximum independent set

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Extensions and consequences of Chvátal-Erdös' theorem
• The Chvátal-Erdős condition for a graph to have a spanning trail
• Chvátal-Erdös type theorems
• Chvátal–Erdős Theorem: Old Theorem with New Aspects
• Long cycles in triangle-free graphs with prescribed independence number and connectivity

Cites work

• A common generalization of Chvátal-Erdös' and Fraisse's sufficient conditions for hamiltonian graphs
• A note on Hamiltonian circuits
• Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
• Chvátal–Erdős Theorem: Old Theorem with New Aspects
• Circumferences of k-connected graphs involving independence numbers
• Extensions and consequences of Chvátal-Erdös' theorem
• Long cycles in triangle-free graphs with prescribed independence number and connectivity
• Long path lemma concerning connectivity and independence number
• Longest cycles in \(k\)-connected graphs with given independence number
• Spanning trees with bounded degrees
• The Chvàtal-Erdős condition for supereulerian graphs and the Hamiltonian index

Cited in

(9)

• Extensions and consequences of Chvátal-Erdös' theorem
• An extension of the Win theorem: counting the number of maximum independent sets
• Counting maximal antichains and independent sets
• Extremal graphs with given stability number and connectivity. I
• The Chvátal-Erdős condition for a graph to have a spanning trail
• Chvátal–Erdős Theorem: Old Theorem with New Aspects
• On the number of maximal independent sets: From Moon–Moser to Hujter–Tuza
• A generalization of the Chvátal-Erdős theorem
• The Chvàtal-Erdős condition for supereulerian graphs and the Hamiltonian index

This page was built for publication: An extension of the Chvátal-Erdős theorem: counting the number of maximum independent sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354602)