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

DOI10.4230/LIPICS.AOFA.2018.18MaRDI QIDQ4993540zbMATH OpenOpenAlexFDO

Authors Michael Drmota, Lander Ramos, Clément Requilé, 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 enumerationcentral limit lawsmaximal independent setmaximal matchingsubcritical graph classes

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)

Recommendations

• Maximal independent sets and maximal matchings in series-parallel and related graph classes
• The maximum degree of series-parallel graphs
• On maximal independent sets of nodes in trees
• Enumeration and limit laws for series-parallel graphs
• Maximum independent number for series-parallel networks

Cites work

• A Note on Independent Sets in Trees
• Analytic combinatorics
• Asymptotic study of subcritical graph classes
• scientific article; zbMATH DE number 3821741 (Why is no real title available?)
• scientific article; zbMATH DE number 1111371 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• On maximal independent sets of nodes in trees
• Random Trees
• Scaling limits of random graphs from subcritical classes
• The degree sequence of random graphs from subcritical classes
• The number of maximal independent sets in a connected graph
• The Number of Maximal Independent Sets in a Tree
• The number of maximum independent sets in graphs
• The number of maximum matchings in a tree
• The structure and maximum number of maximum independent sets in trees
• Tight bounds on maximal and maximum matchings
• Trees with extremal numbers of maximal independent sets including the set of leaves
• Trees with maximum number of maximal matchings

Cited in

(1)

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

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

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