An exact minimum degree condition for Hamilton cycles in oriented graphs

DOI10.1112/JLMS/JDN065zbMATH Open1198.05081arXiv0801.0394OpenAlexW3100779871MaRDI QIDQ3600872FDOQ3600872

Authors: Peter Keevash, Daniela Kühn, Deryk Osthus 

Publication date: 6 February 2009

Published in: Journal of the London Mathematical Society (Search for Journal in Brave)

Abstract: We show that every sufficiently large oriented graph with minimum in- and outdegree at least (3n-4)/8 contains a Hamilton cycle. This is best possible and solves a problem of Thomassen from 1979.

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

Recommendations

• scientific article; zbMATH DE number 147645
• A sufficient condition for oriented graphs to be Hamiltonian
• scientific article; zbMATH DE number 1792615
• Minimum degree conditions for tight Hamilton cycles
• A note on minimum degree condition for Hamilton \((a,b)\)-cycles in hypergraphs
• Hamilton Cycles in Oriented Graphs
• On minimum degree in Hamiltonian path graphs
• scientific article; zbMATH DE number 1047732
• A semiexact degree condition for Hamilton cycles in digraphs
• On the minimum number of Hamiltonian cycles in regular graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45)

Cited In (32)

• Arbitrary Orientations of Hamilton Cycles in Digraphs
• Cycle-factors in oriented graphs
• Path decompositions of tournaments
• Hamilton cycles in dense regular digraphs and oriented graphs
• Hamilton decompositions of regular expanders: applications
• On prisms, Möbius ladders and the cycle space of dense graphs
• Spanning trees of dense directed graphs
• Arbitrary orientations of Hamilton cycles in oriented graphs
• An approximate version of Sumner's universal tournament conjecture
• Tight bounds for powers of Hamilton cycles in tournaments
• Cycles of given length in oriented graphs
• Triangle packings and 1-factors in oriented graphs
• On directed versions of the Corrádi-Hajnal corollary
• An extension of the Hajnal-Szemerédi theorem to directed graphs
• An approximate version of Jackson's conjecture
• Title not available (Why is that?)
• Pósa's conjecture for graphs of order at least 2 × 10⁸
• A survey on Hamilton cycles in directed graphs
• Antidirected subgraphs of oriented graphs
• Degree sequences forcing Hamilton cycles in directed graphs
• Hamilton cycles in sparse robustly expanding digraphs
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Tournaments and Semicomplete Digraphs
• Hamiltonian degree sequences in digraphs
• A note on some embedding problems for oriented graphs
• Antipaths in oriented graphs
• Short cycles in oriented graphs
• A Dirac-Type Result on Hamilton Cycles in Oriented Graphs
• A hypergraph blow-up lemma
• Title not available (Why is that?)
• The minimum number of Hamilton cycles in a Hamiltonian threshold graph of a prescribed order
• A sufficient condition for oriented graphs to be Hamiltonian

This page was built for publication: An exact minimum degree condition for Hamilton cycles in oriented graphs

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