On the number of maximal independent sets: From Moon–Moser to Hujter–Tuza

DOI10.1002/JGT.22971MaRDI QIDQ6094038zbMATH OpenOpenAlexFDO

Authors Cory Palmer, Balázs Patkós

Publication date 9 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

extremal graph theoryinduced (triangle) matchingsmaximal independent setsstability results

Mathematics Subject Classification ID

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

Abstract: We connect two classical results in extremal graph theory concerning the number of maximal independent sets. The maximum number mis$(n)$ of maximal independent sets in an $n$-vertex graph was determined by Moon and Moser. The maximum number mis$$ of maximal independent sets in an $n$-vertex triangle-free graph was determined by Hujter and Tuza. We determine the maximum number mis${}_t(n)$ of maximal independent sets in an $n$-vertex graph containing no induced triangle matching of size $t+1$. We also reprove a stability result of Kahn and Park on the maximum number mis$$ of maximal independent sets in an $n$-vertex triangle-free graphs containing no induced matching of size $t+1$.

Recommendations

• On the maximum number of maximum independent sets
• An extension of the Chvátal-Erdős theorem: counting the number of maximum independent sets
• Generalizing Erdős, Moon and Moser's result -- the number of \(k\)-dominating independent sets
• On the number of maximal independent sets in a graph
• A generalization of maximal independent sets
• Counting maximal independent sets in some \(n\)-gonal cacti
• An extension of the Win theorem: counting the number of maximum independent sets
• On the number of maximum independent sets of graphs
• scientific article; zbMATH DE number 1465674
• On the maximum number of maximum independent sets in connected graphs

Cites work

• A Note on Independent Sets in Trees
• Hypergraph containers
• Independent sets in hypergraphs
• On cliques in graphs
• On the number of maximal independent sets in a graph
• Sharp bound on the number of maximal sum-free subsets of integers
• Stability for maximal independent sets
• The number of maximal independent sets in a connected graph
• The Number of Maximal Independent Sets in a Tree
• The number of maximal independent sets in connected graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• The number of maximal sum-free subsets of integers
• The number of the maximal triangle-free graphs

Cited in

(10)

• An extension of the Win theorem: counting the number of maximum independent sets
• Maximal independent sets in bipartite graphs
• The number of maximal independent sets in connected graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Coverings, matchings and the number of maximal independent sets of graphs
• On the number of maximal independent sets in a graph
• An upper bound for the number of maximal independent sets in a graph
• The minimum number of maximal independent sets in twin-free graphs
• Maximal independent sets in graphs with a given matching number
• The minimum number of maximal independent sets in graphs with given order and independence number

This page was built for publication: On the number of maximal independent sets: From Moon–Moser to Hujter–Tuza

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