Optimal packings of Hamilton cycles in sparse random graphs

DOI10.1137/110849171MaRDI QIDQ4899037zbMATH OpenOpenAlexWikidataFDO

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)

• 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
• Packing tree factors in random and pseudo-random graphs
• On Hamilton cycles in Erdős-Rényi subgraphs of large 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
• Optimal covers with Hamilton cycles in random graphs
• On random \(k\)-out subgraphs of large graphs
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• A note on non-isomorphic edge-color classes in random graphs
• Packing and counting arbitrary Hamilton cycles in random digraphs
• Note on matching preclusion number of random graphs
• Corrádi and Hajnal's theorem for sparse random graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• Hamilton completion and the path cover number of sparse 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)