×

zbMATH — the first resource for mathematics

An exact minimum degree condition for Hamilton cycles in oriented graphs. (English) Zbl 1198.05081
Summary: We show that every sufficiently large oriented graph \(G\) with \({\delta}^{+}(G), {\delta}^{-}(G)\geq (3n-4)/8\) contains a Hamilton cycle. This is best possible and solves a problem of Thomassen from 1979 [C. Thomassen, “Long cycles in digraphs with constraints on the degrees,” Surveys in combinatorics, Proc. 7th Br. Comb. Conf., Cambridge 1979, Lond. Math. Soc. Lect. Note Ser. 38, 211–228 (1979; Zbl 0407.05039)].

MSC:
05C20 Directed graphs (digraphs), tournaments
05C35 Extremal problems in graph theory
05C45 Eulerian and Hamiltonian graphs
PDF BibTeX XML Cite
Full Text: DOI arXiv