A survey on Hamilton cycles in directed graphs

2010/06/03 by Daniela Kühn, Kühn, Daniela, Deryk Osthus +1 · 5 citations
Computer Science · Engineering · Mathematics · #05C20 #05C35 #05C45 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1006.0590

openalex publication_date 2010/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We survey some recent results on long-standing conjectures regarding Hamilton cycles in directed graphs, oriented graphs and tournaments. We also combine some of these to prove the following approximate result towards Kelly's conjecture on Hamilton decompositions of regular tournaments: the edges of every regular tournament can be covered by a set of Hamilton cycles which are `almost' edge-disjoint. We also highlight the role that the notion of `robust expansion' plays in several of the proofs. New and old open problems are discussed.

Citations

• Some Theorems on Abstract Graphs
• Note on Hamilton Circuits

Cited by

• Sufficient conditions for a digraph to contain: a pre-Hamiltonian cycle and cycles of lengths 3 and 4
• From finding a spanning subgraph H to an H-factor
• Hamilton decompositions of regular tripartite tournaments
• An exact Ore-degree condition for Hamilton cycles in oriented graphs
• Hamilton cycles in regular graphs perturbed by a random 2-factor

Related

• Counting Hamilton decompositions of oriented graphs
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Hamilton cycles in highly connected and expanding graphs
• Hamilton Cycles in Dense Regular Digraphs and Oriented Graphs
• Edge-disjoint Hamilton cycles in graphs