Optimal covers with Hamilton cycles in random graphs

DOI10.1007/S00493-014-2956-ZzbMATH Open1340.05153arXiv1203.3868OpenAlexW2047171329MaRDI QIDQ484550FDOQ484550

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

Publication date: 7 January 2015

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On a packing and covering problem
• Title not available (Why is that?)
• A Short Proof of the Factor Theorem for Finite Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Factors of Graphs
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hamilton decompositions of regular expanders: applications
• Approximate Hamilton decompositions of random graphs
• Edge-disjoint Hamilton cycles in random graphs
• Title not available (Why is that?)
• Optimal packings of Hamilton cycles in sparse random graphs
• Hamilton cycles in highly connected and expanding graphs
• On two Hamilton cycle problems in random graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• On covering expander graphs by Hamilton cycles

Cited In (7)

• Optimal packings of Hamilton cycles in sparse random graphs
• On \(r\)-regular subgraphs with Hamiltonian cycles in graphs with many edges
• 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
• Optimal path and cycle decompositions of dense quasirandom graphs
• On covering expander graphs by Hamilton cycles

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)