Approximate Hamilton decompositions of random graphs

DOI10.1002/RSA.20365MaRDI QIDQ3119046zbMATH OpenOpenAlexFDO

Authors 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

binomial random graphsHamilton cyclesHamilton decomposition

Mathematics Subject Classification ID

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

Abstract: We show that if pn >> log n, the binomial random graph G_{n,p} has an approximate Hamilton decomposition. More precisely, we show that in this range G_{n,p} contains a set of edge-disjoint Hamilton cycles covering almost all of its edges. This is best possible in the sense that the condition that pn >> log n is necessary.

Recommendations

• Edge-disjoint Hamilton cycles in random graphs
• Optimal packings of Hamilton cycles in sparse random graphs
• Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
• On two Hamilton cycle problems in random graphs
• Hamiltonian decompositions of random bipartite regular graphs.

Cites work

• Edge-disjoint Hamilton cycles in graphs
• Edge-Disjoint Hamiltonian Paths and Cycles in Tournaments
• Hamilton decompositions of regular tournaments
• Hamiltonian circuits in random graphs
• scientific article; zbMATH DE number 3801730 (Why is no real title available?)
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• On two Hamilton cycle problems in random graphs
• Packing Hamilton cycles in random and pseudo-random hypergraphs
• Packing tight Hamilton cycles in 3-uniform hypergraphs
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
• Sparse pseudo‐random graphs are Hamiltonian
• The Factors of Graphs

Cited in

(14)

• Hamiltonian decompositions of random bipartite regular 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
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• scientific article; zbMATH DE number 4031730 (Why is no real title available?)
• Packing tree factors in random and pseudo-random graphs
• Optimal covers with Hamilton cycles in random graphs
• Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs
• Edge-disjoint Hamilton cycles in random graphs
• Decomposing random graphs into few cycles and edges
• On covering expander graphs by Hamilton cycles
• Hamilton cycles in pseudorandom graphs
• Hamilton cycles in pseudorandom graphs (extended abstract)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3119046)