Edge-disjoint Hamilton cycles in random graphs

DOI10.1002/rsa.20510zbMath1312.05124arXiv1104.4412OpenAlexW2010688605WikidataQ105583238 ScholiaQ105583238MaRDI QIDQ5252256

Daniela Kühn, Fiachra Knox, Deryk Osthus

Publication date: 29 May 2015

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

packingsrandom graphsHamilton cycles

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)

Related Items (31)

Clique decompositions of multipartite graphs and completion of Latin squares ⋮ Proof of the 1-factorization and Hamilton Decomposition Conjectures ⋮ The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹 ⋮ Packing Directed Hamilton Cycles Online ⋮ Packing Hamilton Cycles Online ⋮ Hitting Time of Edge Disjoint Hamilton Cycles in Random Subgraph Processes on Dense Base Graphs ⋮ Counting and packing Hamilton cycles in dense graphs and oriented graphs ⋮ The number of Hamiltonian decompositions of regular graphs ⋮ Packing tree factors in random and pseudo-random graphs ⋮ Packing arborescences in random digraphs ⋮ Proof of Komlós's conjecture on Hamiltonian subsets ⋮ Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor ⋮ Perfectly packing graphs with bounded degeneracy and many leaves ⋮ Threshold for Steiner triple systems ⋮ Graph and hypergraph packing ⋮ Decomposing Random Graphs into Few Cycles and Edges ⋮ Minimalist designs ⋮ On Hamilton cycles in Erdős‐Rényi subgraphs of large graphs ⋮ Packing Loose Hamilton Cycles ⋮ On prisms, Möbius ladders and the cycle space of dense graphs ⋮ Optimal path and cycle decompositions of dense quasirandom graphs ⋮ Packing and counting arbitrary Hamilton cycles in random digraphs ⋮ Almost all Steiner triple systems are almost resolvable ⋮ Packing Arborescences in Random Digraphs ⋮ Optimal covers with Hamilton cycles in random graphs ⋮ Packing, counting and covering Hamilton cycles in random directed graphs ⋮ On covering expander graphs by hamilton cycles ⋮ Optimal packings of bounded degree trees ⋮ Random directed graphs are robustly Hamiltonian ⋮ Note on matching preclusion number of random graphs ⋮ On the decomposition threshold of a given graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal covers with Hamilton cycles in random graphs
• Paley graphs have Hamilton decompositions
• Edge-disjoint Hamilton cycles in graphs
• On two Hamilton cycle problems in random graphs
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Packing tight Hamilton cycles in 3-uniform hypergraphs
• Packing hamilton cycles in random and pseudo-random hypergraphs
• Packing Tight Hamilton Cycles in Uniform Hypergraphs
• Approximate Hamilton decompositions of random graphs
• On the Resilience of Hamiltonicity and Optimal Packing of Hamilton Cycles in Random Graphs
• Multicolored Hamilton Cycles and Perfect Matchings in Pseudorandom Graphs
• Sparse pseudo‐random graphs are Hamiltonian
• Optimal Packings of Hamilton Cycles in Sparse Random Graphs
• Optimal Packings of Hamilton Cycles in Graphs of High Minimum Degree
• On covering expander graphs by hamilton cycles
• The Factorization of Linear Graphs
• The Factors of Graphs

This page was built for publication: Edge-disjoint Hamilton cycles in random graphs