Approximate Hamilton decompositions of random graphs

DOI10.1002/rsa.20365zbMath1236.05181arXiv1006.1268MaRDI 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 cycles; Hamilton decomposition; binomial random graphs

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

05C38: Paths and cycles

05C45: Eulerian and Hamiltonian graphs

Related Items

Hitting Time of Edge Disjoint Hamilton Cycles in Random Subgraph Processes on Dense Base Graphs, Edge-disjoint Hamilton cycles in random graphs, On covering expander graphs by hamilton cycles, Counting and packing Hamilton cycles in dense graphs and oriented graphs, Packing tree factors in random and pseudo-random graphs, Optimal covers with Hamilton cycles in 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

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