Optimal packings of Hamilton cycles in sparse random graphs

DOI10.1137/110849171MaRDI QIDQ4899037zbMATHOpenAlexWikidataFDO

Authors Michael Krivelevich, Wojciech Samotij

Publication date 4 January 2013

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

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

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)

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.

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

Cited in

(28)

• Packing loose Hamilton cycles
• Hamilton decompositions of regular expanders: applications
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• Corrádi and Hajnal's theorem for sparse random graphs
• Recent advances on the Hamiltonian problem: survey III
• Packing tree factors in random and pseudo-random graphs
• A note on non-isomorphic edge-color classes in random graphs
• Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs
• Packing directed Hamilton cycles online
• On prisms, Möbius ladders and the cycle space of dense graphs
• Approximate Hamilton decompositions of random graphs
• Note on matching preclusion number of random graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• On random \(k\)-out subgraphs of large graphs
• Packing Hamilton cycles online
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• On Hamilton cycles in Erdős-Rényi subgraphs of large graphs
• Packing and counting arbitrary Hamilton cycles in random digraphs
• On covering expander graphs by Hamilton cycles
• A note on spanning \(K_r\)-cycles in random graphs
• Packing arborescences in random digraphs
• Optimal covers with Hamilton cycles in random graphs
• Edge-disjoint Hamilton cycles in random graphs
• Optimal packings of Hamilton cycles in graphs of high minimum degree
• Hamilton completion and the path cover number of sparse random graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Random directed graphs are robustly Hamiltonian
• Packing, counting and covering Hamilton cycles in random directed graphs

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)