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