A survey on Hamilton cycles in directed graphs

DOI10.1016/J.EJC.2011.09.030zbMATH Open1239.05114arXiv1006.0590OpenAlexW2036286064MaRDI QIDQ412269FDOQ412269

Authors: Daniela Kühn, Deryk Osthus 

Publication date: 4 May 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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.

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

Recommendations

• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hamilton decompositions of regular expanders: applications
• Counting Hamilton decompositions of oriented graphs
• Hamilton decompositions of regular tournaments
• Approximate Hamilton decompositions of robustly expanding regular digraphs

zbMATH Keywords

tournamentsoriented graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• On Hamilton's ideals
• Sparse pseudo‐random graphs are Hamiltonian
• Proof of the Seymour conjecture for large graphs
• Title not available (Why is that?)
• Testing subgraphs in directed graphs
• Note on Hamilton Circuits
• Degree conditions for k‐ordered hamiltonian graphs
• Title not available (Why is that?)
• Some Theorems on Abstract Graphs
• A note on Hamiltonian circuits
• Title not available (Why is that?)
• Onk-ordered Hamiltonian graphs
• Hamilton cycles in regular 2-connected graphs
• Title not available (Why is that?)
• Hamiltonian degree sequences in digraphs
• A proof of Sumner's universal tournament conjecture for large tournaments
• Title not available (Why is that?)
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• The maximum number of Hamiltonian paths in tournaments
• Global connectivity and expansion: long cycles and factors in \(f\)-connected graphs
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hamilton Cycles in Oriented Graphs
• Hamiltonian Cycles in Regular Tournaments
• Decomposing \(k\)-arc-strong tournaments into strong spanning subdigraphs
• On the Number of Hamiltonian Cycles in a Tournament
• Title not available (Why is that?)
• Edge-disjoint Hamilton cycles in graphs
• Sufficient Conditions for Circuits in Graphs^†
• Advances on the Hamiltonian problem -- a survey
• Title not available (Why is that?)
• Oriented Hamiltonian paths in tournaments: A proof of Rosenfeld's conjecture
• Paths and Cycles in Tournaments
• Partitioning vertices of a tournament into independent cycles
• Complementary cycles of all lengths in tournaments
• Triangle packings and 1-factors in oriented graphs
• A Chvátal-Erdős condition for Hamilton cycles in digraphs
• A Hamiltonian decomposition of \(K^*_{2m},2m\geq 8\)
• An Ore-type condition implying a digraph to be pancyclic
• A new sufficient condition for a digraph to be Hamiltonian
• Oriented Hamiltonian cycles in tournaments
• Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
• Une condition suffisante d'existence d'un circuit Hamiltonien dans un graphe oriente
• A note on some embedding problems for oriented graphs
• A semiexact degree condition for Hamilton cycles in digraphs
• Finding Hamilton cycles in robustly expanding digraphs
• A Dirac-Type Result on Hamilton Cycles in Oriented Graphs
• Hamilton decompositions of regular tournaments
• Cycles in digraphs– a survey
• Edge-Disjoint Hamiltonian Paths and Cycles in Tournaments
• Title not available (Why is that?)
• Pancyclic oriented graphs
• Title not available (Why is that?)
• Combinatorial and computational aspects of graph packing and graph decomposition
• Oriented hamilton cycles in digraphs
• Title not available (Why is that?)
• On the Bollobás–Eldridge Conjecture for Bipartite Graphs
• Title not available (Why is that?)
• Hamilton cycles in highly connected and expanding graphs
• Arbitrary orientations of Hamilton cycles in oriented graphs
• An approximate version of Sumner's universal tournament conjecture
• A note on the number of Hamiltonian paths in strong tournaments
• Powers of Hamilton cycles in tournaments
• \(k\)-Ordered Hamilton cycles in digraphs
• Cycles of given length in oriented graphs

Cited In (34)

• Arbitrary Orientations of Hamilton Cycles in Digraphs
• A random walk approach to linear statistics in random tournament ensembles
• The robust component structure of dense regular graphs and applications
• Hamilton cycles in dense regular digraphs and oriented graphs
• Hamilton decompositions of regular expanders: applications
• Recent advances on the Hamiltonian problem: survey III
• Hamilton powers of Eulerian digraphs
• Approximate Hamilton decompositions of robustly expanding regular digraphs
• An improvement of Lichiardopol's theorem on disjoint cycles in tournaments
• A new sufficient condition for a Digraph to be Hamiltonian-A proof of Manoussakis Conjecture
• Tight bounds for powers of Hamilton cycles in tournaments
• Sufficient conditions for Hamiltonian cycles in bipartite digraphs
• Oriented discrepancy of Hamilton cycles
• Hamiltonian problems in directed graphs with simple row patterns
• A multi-threading algorithm to detect and remove cycles in vertex- and arc-weighted digraph
• A new sufficient condition for a 2-strong digraph to be Hamiltonian
• The ratio of the numbers of odd and even cycles in outerplanar graphs
• Computational complexity of counting coincidences
• A survey: Hamiltonian cycles in Cayley graphs
• Hamilton cycles in sparse robustly expanding digraphs
• Cayley graph associated to a semihypergroup
• Hamiltonicity, pancyclicity, and full cycle extendability in multipartite tournaments
• Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs
• On the maximum number of spanning copies of an orientation in a tournament
• Counting Hamilton decompositions of oriented graphs
• Properly colored cycles of different lengths in edge-colored complete graphs
• Transversal Hamilton cycle in hypergraph systems
• Hamiltonian cycles above expectation in \(r\)-graphs and quasi-random \(r\)-graphs
• A note on the Hamiltonian circuit problem on directed path graphs
• Long directed rainbow cycles and rainbow spanning trees
• Hamiltonian cycles and paths in Cayley graphs and digraphs---a survey
• Spanning Eulerian subdigraphs avoiding \(k\) prescribed arcs in tournaments
• Edge-disjoint properly colored cycles in edge-colored complete graphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments

This page was built for publication: A survey on Hamilton cycles in directed graphs

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