Hamilton Cycles in Dense Regular Digraphs and Oriented Graphs

2022/03/18 by Allan Lo, Lo, Allan, Viresh Patel +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2203.10112

Abstract

We prove that for every ε > 0 there exists n₀=n₀(ε) such that every regular oriented graph on n > n₀ vertices and degree at least (1/4 + ε)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ühn and Osthus about the Hamiltonicity of regular directed graphs with suitable degree and connectivity conditions.

Cited by

• Hamilton decompositions of regular tripartite tournaments

Related

• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Counting Hamilton decompositions of oriented graphs
• A survey on Hamilton cycles in directed graphs
• Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree
• The regularity method for graphs and digraphs