On large matchings and cycles in sparse random graphs

DOI10.1016/0012-365X(86)90171-8zbMath0628.05051WikidataQ57401631 ScholiaQ57401631MaRDI QIDQ1092926

Alan M. Frieze

Publication date: 1986

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

random graphHamilton cycleslarge cycleslarge matchings

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Related Items (25)

Finding Hamilton cycles in sparse random graphs ⋮ On the number of circuits in random graphs ⋮ Crux and Long Cycles in Graphs ⋮ Cycles in a random graph near the critical point ⋮ Partitioning random graphs into large cycles ⋮ The automorphism group of random graphs with a given number of edges ⋮ A note on long cycles in sparse random graphs ⋮ Cycle lengths in sparse random graphs ⋮ A scaling limit for the length of the longest cycle in a sparse random digraph ⋮ Rainbow trees in uniformly edge‐colored graphs ⋮ Hamilton completion and the path cover number of sparse random graphs ⋮ Turán‐type problems for long cycles in random and pseudo‐random graphs ⋮ Scaling window for mean-field percolation of averages ⋮ An analogue of the Erdős-Gallai theorem for random graphs ⋮ Cycles in random graphs ⋮ On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph ⋮ Embedding nearly-spanning bounded degree trees ⋮ On depth first search trees in \(m\)-out digraphs ⋮ Paths and cycles in random subgraphs of graphs with large minimum degree ⋮ A scaling limit for the length of the longest cycle in a sparse random graph ⋮ Random perturbation of sparse graphs ⋮ The Kőnig graph process ⋮ Large cycles in random generalized Johnson graphs ⋮ Long paths and cycles in random subgraphs of graphs with large minimum degree ⋮ Longest cycles in sparse random digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Long paths in sparse random graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• The longest path in a random graph
• Hamiltonian circuits in random graphs
• On the existence of Hamiltonian cycles in a class of random graphs
• Clutter percolation and random graphs
• Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk
• On the existence of a factor of degree one of a connected random graph

This page was built for publication: On large matchings and cycles in sparse random graphs