Hamilton cycles in dense regular digraphs and oriented graphs

DOI10.1016/J.JCTB.2023.09.004MaRDI QIDQ6144396zbMATH OpenOpenAlexFDO

Authors Allan Lo, Viresh Patel, M. Yildiz

Publication date 29 January 2024

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

digraphHamilton cycleoriented graphregularrobust expander

Mathematics Subject Classification ID

Combinatorics (05-XX)

Abstract: We prove that for every $varepsilon>0$ there exists $n_0=n_0(varepsilon)$ such that every regular oriented graph on $n>n_0$ vertices and degree at least $(1/4+varepsilon)n$ has a Hamilton cycle. This establishes an approximate version of a conjecture of Jackson from 1981. We also establish a result related to a conjecture of K"uhn and Osthus about the Hamiltonicity of regular directed graphs with suitable degree and connectivity conditions.

Recommendations

• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• A Dirac-Type Result on Hamilton Cycles in Oriented Graphs
• Hamilton Cycles in Oriented Graphs

Cites work

• A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs
• A survey on Hamilton cycles in directed graphs
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• Dominating cycles in regular 3-connected graphs
• Hamilton cycles in regular 2-connected graphs
• Hamilton cycles in sparse robustly expanding digraphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hamilton decompositions of regular expanders: applications
• Hamiltonian degree sequences in digraphs
• scientific article; zbMATH DE number 3149611 (Why is no real title available?)
• scientific article; zbMATH DE number 3902690 (Why is no real title available?)
• Probability and Computing
• Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs
• Some Theorems on Abstract Graphs
• The robust component structure of dense regular graphs and applications

Cited in

(1)

• Cycle partitions in dense regular digraphs and oriented graphs

This page was built for publication: Hamilton cycles in dense regular digraphs and oriented graphs

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