Maximum matchings in a class of random graphs

DOI10.1016/0095-8956(86)90077-8zbMath0629.05057WikidataQ57401629 ScholiaQ57401629MaRDI QIDQ1093654

Alan M. Frieze

Publication date: 1986

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(86)90077-8

zbMATH Keywords

random graph; perfect matching

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Related Items

Random near-regular graphs and the node packing problem, An exact threshold theorem for random graphs and the node-packing problem, Matchings and cycle covers in random digraphs, Matching theory -- a sampler: From Dénes König to the present, Existence of a perfect matching in a random (\(1+e^{-1}\))-out bipartite graph, Edge disjoint spanning trees in random graphs

Cites Work

• Unnamed Item
• On the connectivity of random m-orientable graphs and digraphs
• Random near-regular graphs and the node packing problem
• An exact threshold theorem for random graphs and the node-packing problem
• Matchings in random regular bipartite digraphs
• One-factor in random graphs based on vertex choice
• On the existence of Hamiltonian cycles in a class of random graphs
• Paths, Trees, and Flowers
• The Factorization of Linear Graphs