Optimal covers with Hamilton cycles in random graphs

DOI10.1007/S00493-014-2956-ZzbMATHOpenAlexMaRDI QIDQ484550FDO

Authors Dan Hefetz, Daniela Kühn, John Lapinskas, Deryk Osthus

Publication date 7 January 2015

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

optimal packingrandom graphsHamilton cyclesedge covering

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A packing of a graph G with Hamilton cycles is a set of edge-disjoint Hamilton cycles in G. Such packings have been studied intensively and recent results imply that a largest packing of Hamilton cycles in G_n,p a.a.s. has size lfloor delta(G_n,p) /2 floor. Glebov, Krivelevich and Szab'o recently initiated research on the `dual' problem, where one asks for a set of Hamilton cycles covering all edges of G. Our main result states that for log^{117}n / n < p < 1-n^{-1/8}, a.a.s. the edges of G_n,p can be covered by lceil Delta(G_n,p)/2 ceil Hamilton cycles. This is clearly optimal and improves an approximate result of Glebov, Krivelevich and Szab'o, which holds for p > n^{-1+eps}. Our proof is based on a result of Knox, K"uhn and Osthus on packing Hamilton cycles in pseudorandom graphs.

Recommendations

• On covering expander graphs by Hamilton cycles
• Optimal packings of Hamilton cycles in sparse random graphs
• Edge-disjoint Hamilton cycles in random graphs
• Powers of Hamilton cycles in pseudorandom graphs
• On two Hamilton cycle problems in random graphs

Cites work

• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3922707 (Why is no real title available?)
• scientific article; zbMATH DE number 3950585 (Why is no real title available?)
• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A Short Proof of the Factor Theorem for Finite Graphs
• Approximate Hamilton decompositions of random graphs
• Edge-disjoint Hamilton cycles in random graphs
• Hamilton cycles in highly connected and expanding graphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hamilton decompositions of regular expanders: applications
• On a packing and covering problem
• On covering expander graphs by Hamilton cycles
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• On two Hamilton cycle problems in random graphs
• Optimal packings of Hamilton cycles in sparse random graphs
• The Factors of Graphs

Cited in

(6)

• On \(r\)-regular subgraphs with Hamiltonian cycles in graphs with many edges
• Optimal packings of Hamilton cycles in sparse random graphs
• On covering expander graphs by Hamilton cycles
• Edge-disjoint Hamilton cycles in random graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Packing, counting and covering Hamilton cycles in random directed graphs

This page was built for publication: Optimal covers with Hamilton cycles in random graphs

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