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

Hamilton cyclepackingrandom graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) 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

(32)

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