Approximate Hamilton decompositions of random graphs

DOI10.1002/rsa.20365zbMath1236.05181arXiv1006.1268OpenAlexW2006567887MaRDI QIDQ3119046

Fiachra Knox, Daniela Kühn, Deryk Osthus

Publication date: 7 March 2012

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1006.1268

zbMATH Keywords

Hamilton cyclesHamilton decompositionbinomial random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Related Items (9)

Hitting Time of Edge Disjoint Hamilton Cycles in Random Subgraph Processes on Dense Base Graphs ⋮ Counting and packing Hamilton cycles in dense graphs and oriented graphs ⋮ Packing tree factors in random and pseudo-random graphs ⋮ Hamilton decompositions of regular expanders: applications ⋮ Recent advances on the Hamiltonian problem: survey III ⋮ On prisms, Möbius ladders and the cycle space of dense graphs ⋮ Optimal covers with Hamilton cycles in random graphs ⋮ On covering expander graphs by hamilton cycles ⋮ Edge-disjoint Hamilton cycles in random graphs

Cites Work

• Unnamed Item
• Edge-disjoint Hamilton cycles in graphs
• On two Hamilton cycle problems in random graphs
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Hamiltonian circuits in random graphs
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
• Packing tight Hamilton cycles in 3-uniform hypergraphs
• Packing hamilton cycles in random and pseudo-random hypergraphs
• Hamilton decompositions of regular tournaments
• Edge-Disjoint Hamiltonian Paths and Cycles in Tournaments
• Sparse pseudo‐random graphs are Hamiltonian
• The Factors of Graphs

This page was built for publication: Approximate Hamilton decompositions of random graphs