Maximal independent sets in graphs with a given matching number

DOI10.1016/J.DISC.2025.114880MaRDI QIDQ6883643zbMATH OpenFDO

Authors Yongtang Shi, Jianhua Tu, Ziyuan Wang

Publication date 16 December 2025

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

extremal combinatoricscountingmatching numbermaximal independent sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Cites work

• A Note on Independent Sets in Trees
• Constraints on the number of maximal independent sets in graphs
• Coverings, matchings and the number of maximal independent sets of graphs
• Matching theory
• Maximal and maximum independent sets in graphs with at mostr cycles
• Maximal independent sets in graphs with at mostr cycles
• On cliques in graphs
• On the number of maximal independent sets: From Moon–Moser to Hujter–Tuza
• TWO THEOREMS IN GRAPH THEORY
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• The Number of Maximal Independent Sets in a Tree
• The maximum number of maximal independent sets in unicyclic connected graphs
• The number of maximal independent sets in a connected graph
• The number of maximal independent sets in connected graphs
• The number of maximal independent sets in connected triangle-free graphs
• The number of maximal independent sets in trees with a given number of leaves
• Trees with extremal numbers of maximal independent sets including the set of leaves

Cited in

(1)

• Maximizing the number of maximal independent sets in graphs with a given matching number

This page was built for publication: Maximal independent sets in graphs with a given matching number

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