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

DOI10.1007/S11401-019-0141-9MaRDI QIDQ2002161zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• A common generalization of Chvátal-Erdös' and Fraisse's sufficient conditions for hamiltonian graphs
• A note on Hamiltonian circuits
• An extension of the Chvátal-Erdős theorem: counting the number of maximum independent sets
• 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
• Factors and factorizations of graphs. Proof techniques in factor theory
• Long cycles in triangle-free graphs with prescribed independence number and connectivity
• On a conjecture of Las Vergnas concerning certain spanning trees in graphs
• Spanning trees with bounded degrees
• The Chvàtal-Erdős condition for supereulerian graphs and the Hamiltonian index

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)