Counting and packing Hamilton cycles in dense graphs and oriented graphs

DOI10.1016/J.JCTB.2016.06.001zbMATH Open1350.05063arXiv1212.4667OpenAlexW1554423888MaRDI QIDQ345082FDOQ345082

Authors: Asaf Ferber, Michael Krivelevich, Benny Sudakov 

Publication date: 25 November 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: We present a general method for counting and packing Hamilton cycles in dense graphs and oriented graphs, based on permanent estimates. We utilize this approach to prove several extremal results. In particular, we show that every nearly $cn$-regular oriented graph on $n$ vertices with $c>3/8$ contains $(cn/e{)}^n(1+o(1){)}^n$ directed Hamilton cycles. This is an extension of a result of Cuckler, who settled an old conjecture of Thomassen about the number of Hamilton cycles in regular tournaments. We also prove that every graph $G$ on $n$ vertices of minimum degree at least $(1/2+varepsilon)n$ contains at least $(1-varepsilon)extrm{reg}_{even}(G)/2$ edge-disjoint Hamilton cycles, where $eg(G)$ is the maximum emph{even} degree of a spanning regular subgraph of $G$. This establishes an approximate version of a conjecture of K"uhn, Lapinskas and Osthus.

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

Recommendations

• Counting and packing Hamilton \(\ell\)-cycles in dense hypergraphs
• scientific article; zbMATH DE number 1003265
• On the number of Hamiltonian cycles in Hamiltonian dense graphs
• Approximately Counting Hamilton Paths and Cycles in Dense Graphs
• Packing and counting arbitrary Hamilton cycles in random digraphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• Packing tight Hamilton cycles in uniform hypergraphs
• Packing Hamilton cycles in random and pseudo-random hypergraphs

zbMATH Keywords

countingpackingHamilton cyclesoriented graphs

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Enumeration in graph theory (05C30) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Some Theorems on Abstract Graphs
• Problems and results in extremal combinatorics. I.
• Title not available (Why is that?)
• Hamiltonian circuits in random graphs
• Title not available (Why is that?)
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Title not available (Why is that?)
• Hamiltonian degree sequences in digraphs
• Minimum degree of a graph and the existence of k-factors
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• On the number of Hamiltonian cycles in Dirac graphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• The maximum number of Hamiltonian paths in tournaments
• Hamilton decompositions of regular expanders: applications
• Approximate Hamilton decompositions of robustly expanding regular digraphs
• Approximate Hamilton decompositions of random graphs
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• Local resilience of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the number of Hamilton cycles in pseudo-random graphs
• Hamilton Cycles in Oriented Graphs
• Title not available (Why is that?)
• Optimal packings of Hamilton cycles in graphs of high minimum degree
• Edge-disjoint Hamilton cycles in random graphs
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• Hamiltonian Cycles in Regular Tournaments
• On the Number of Hamilton Cycles in Sparse Random Graphs
• Title not available (Why is that?)
• On the Number of Hamiltonian Cycles in a Tournament
• Title not available (Why is that?)
• Edge-disjoint Hamilton cycles in graphs
• Hamiltonian cycles in Dirac graphs

Cited In (18)

• Random directed graphs are robustly Hamiltonian
• Hamilton cycles in dense regular digraphs and oriented graphs
• Hamilton decompositions of regular expanders: applications
• The number of bounded‐degree spanning trees
• Cycle lengths in randomly perturbed graphs
• Decomposing hypergraphs into cycle factors
• Hamilton cycles in sparse robustly expanding digraphs
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• Packing, counting and covering Hamilton cycles in random directed graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• On the maximum number of spanning copies of an orientation in a tournament
• Compatible powers of Hamilton cycles in dense graphs
• The number of Hamiltonian decompositions of regular graphs
• Hamiltonian cycles above expectation in \(r\)-graphs and quasi-random \(r\)-graphs
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• On the number of Hamiltonian cycles in Hamiltonian dense graphs
• Optimal packings of Hamilton cycles in graphs of high minimum degree
• Compatible Hamilton cycles in Dirac graphs

This page was built for publication: Counting and packing Hamilton cycles in dense graphs and oriented graphs

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