Counting and packing Hamilton cycles in dense graphs and oriented graphs

DOI10.1016/J.JCTB.2016.06.001MaRDI QIDQ345082zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

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
• Compatible Hamilton cycles in Dirac graphs
• Optimal packings of Hamilton cycles in graphs of high minimum degree

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)