Maximal independent sets and maximal matchings in series-parallel and related graph classes

DOI10.4230/LIPIcs.AofA.2018.18zbMath1482.05252OpenAlexW2811238923MaRDI QIDQ4993540

Michael Drmota, Clément Requilé, Lander Ramos, Juanjo Rué

Publication date: 15 June 2021

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8911/pdf/LIPIcs-AofA-2018-18.pdf/

zbMATH Keywords

asymptotic enumerationmaximal matchingmaximal independent setsubcritical graph classescentral limit laws

Mathematics Subject Classification ID

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

Related Items (1)

Maximal independent sets and maximal matchings in series-parallel and related graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scaling limits of random graphs from subcritical classes
• The number of maximum matchings in a tree
• Trees with maximum number of maximal matchings
• Trees with extremal numbers of maximal independent sets including the set of leaves
• The number of maximal independent sets in a connected graph
• Tight bounds on maximal and maximum matchings
• Asymptotic Study of Subcritical Graph Classes
• Random Trees
• The Degree Sequence of Random Graphs from Subcritical Classes
• The Number of Maximal Independent Sets in a Tree
• A Note on Independent Sets in Trees
• On maximal independent sets of nodes in trees
• The structure and maximum number of maximum independent sets in trees
• The number of maximum independent sets in graphs

This page was built for publication: Maximal independent sets and maximal matchings in series-parallel and related graph classes