Optimal packings of Hamilton cycles in sparse random graphs

DOI10.1137/110849171zbMATH Open1256.05194arXiv1109.5341OpenAlexW2066266229WikidataQ105584137 ScholiaQ105584137MaRDI QIDQ4899037FDOQ4899037

Authors: Michael Krivelevich, Wojciech Samotij 

Publication date: 4 January 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We prove that there exists a positive constant epsilon such that if log n / n le p le n^{-1+epsilon}, then asymptotically almost surely the random graph G ~ G(n,p) contains a collection of lfloor delta(G)/2 floor edge-disjoint Hamilton cycles.

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

Recommendations

• Edge-disjoint Hamilton cycles in random graphs
• On the Number of Hamilton Cycles in Sparse Random Graphs
• On two Hamilton cycle problems in random graphs
• Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk
• Optimal covers with Hamilton cycles in random graphs

zbMATH Keywords

random graphHamilton cyclepacking

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cited In (29)

• Random directed graphs are robustly Hamiltonian
• Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• 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
• On Hamilton cycles in Erdős-Rényi subgraphs of large graphs
• Packing tree factors in random and pseudo-random graphs
• Packing loose Hamilton cycles
• Approximate Hamilton decompositions of random graphs
• A note on spanning \(K_r\)-cycles in random graphs
• Packing arborescences in random digraphs
• Packing Hamilton cycles online
• Packing directed Hamilton cycles online
• Edge-disjoint Hamilton cycles in random graphs
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• A note on non-isomorphic edge-color classes in random graphs
• On random \(k\)-out subgraphs of large graphs
• Packing and counting arbitrary Hamilton cycles in random digraphs
• Optimal covers with Hamilton cycles in random graphs
• Proof of Komlós's conjecture on Hamiltonian subsets
• Packing, counting and covering Hamilton cycles in random directed graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Corrádi and Hajnal's theorem for sparse random graphs
• Optimal path and cycle decompositions of dense quasirandom graphs
• Note on matching preclusion number of random graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• On covering expander graphs by Hamilton cycles
• Optimal packings of Hamilton cycles in graphs of high minimum degree

This page was built for publication: Optimal packings of Hamilton cycles in sparse random graphs

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