Small maximal matchings of random cubic graphs

DOI10.1002/JGT.20434MaRDI QIDQ3652558zbMATH OpenOpenAlexFDO

Authors

Publication date 18 December 2009

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

Full work available at URL https://doi.org/10.1002/jgt.20434

zbMATH Keywords

random cubic graphssmallest maximal matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Small maximal matchings in random graphs.
• scientific article; zbMATH DE number 1696620
• Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs
• scientific article; zbMATH DE number 1512672
• Minimum maximal matchings in cubic graphs

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Almost all regular graphs are hamiltonian
• Differential equations for random processes and random graphs
• Edge Dominating Sets in Graphs
• Global optimization method for solving the minimum maximal flow problem
• scientific article; zbMATH DE number 3729228 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1174626 (Why is no real title available?)
• scientific article; zbMATH DE number 1933049 (Why is no real title available?)
• scientific article; zbMATH DE number 944215 (Why is no real title available?)
• Minimum Edge Dominating Sets
• Minimum independent dominating sets of random cubic graphs
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• The asymptotic connectivity of labelled regular graphs

Cited in

(7)

• Small maximal matchings in random graphs.
• Maximum induced matchings of random cubic graphs
• Minimum maximal matchings in cubic graphs
• scientific article; zbMATH DE number 1696620 (Why is no real title available?)
• scientific article; zbMATH DE number 437559 (Why is no real title available?)
• scientific article; zbMATH DE number 1512672 (Why is no real title available?)
• Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs

This page was built for publication: Small maximal matchings of random cubic graphs

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