Maximum matchings in a class of random graphs

DOI10.1016/0095-8956(86)90077-8zbMath0629.05057OpenAlexW2054534432WikidataQ57401629 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 graphperfect matching

Mathematics Subject Classification ID

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

Related Items

An exact threshold theorem for random graphs and the node-packing problem ⋮ Corrigendum to: ``Existence of a perfect matching in a random \((1+e^{-1})\)-out bipartite graph ⋮ Perfect fractional matchings in \(k\)-out hypergraphs ⋮ Power of \(k\) choices in the semi-random graph process ⋮ Existence of a perfect matching in a random (\(1+e^{-1}\))-out bipartite graph ⋮ Rainbow Spanning Trees in Randomly Colored \(\boldsymbol{G}_{\boldsymbol{k}-\boldsymbol{out}}\) ⋮ On randomk-out subgraphs of large graphs ⋮ Minimum-weight combinatorial structures under random cost-constraints ⋮ Matchings and cycle covers in random digraphs ⋮ Matching theory -- a sampler: From Dénes König to the present ⋮ Edge disjoint spanning trees in random graphs ⋮ Karp–Sipser on Random Graphs with a Fixed Degree Sequence ⋮ Rank of the Vertex-Edge Incidence Matrix of r-Out Hypergraphs ⋮ Random near-regular graphs and the node packing problem

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