An extension of the Win theorem: counting the number of maximum independent sets

DOI10.1007/S11401-019-0141-9zbMATH Open1415.05081OpenAlexW2942825434MaRDI QIDQ2002161FDOQ2002161

Authors: Yanyan Li 

Publication date: 11 July 2019

Published in: Chinese Annals of Mathematics. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11401-019-0141-9

Recommendations

• An extension of the Chvátal-Erdős theorem: counting the number of maximum independent sets
• On the maximum number of maximum independent sets
• Counting maximal independent sets in some \(n\)-gonal cacti
• On the number of maximal independent sets: From Moon–Moser to Hujter–Tuza
• A generalization of maximal independent sets
• Maximizing the number of independent sets of a fixed size
• On the number of maximal independent sets in a graph
• The number of maximum independent sets in graphs
• Counting the maximal independent sets in power set graphs
• Extremal problems for independent set enumeration

zbMATH Keywords

connectivitymaximum independent set\(k\)-ended tree

Mathematics Subject Classification ID

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

Cites Work

• On a conjecture of Las Vergnas concerning certain spanning trees in graphs
• Spanning trees with bounded degrees
• A note on Hamiltonian circuits
• Factors and factorizations of graphs. Proof techniques in factor theory
• Circumferences of \(k\)-connected graphs involving independence numbers
• Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
• The Chvàtal-Erdős condition for supereulerian graphs and the Hamiltonian index
• Long cycles in triangle-free graphs with prescribed independence number and connectivity
• A common generalization of Chvátal-Erdös' and Fraisse's sufficient conditions for hamiltonian graphs
• Extensions and consequences of Chvátal-Erdös' theorem
• Chvátal–Erdős Theorem: Old Theorem with New Aspects
• An extension of the Chvátal-Erdős theorem: counting the number of maximum independent sets

Cited In (2)

• A note on the independence number, connectivity and \(k\)-ended tree
• On the number of maximal independent sets: From Moon–Moser to Hujter–Tuza

This page was built for publication: An extension of the Win 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 Q2002161)