Semi-degree threshold for anti-directed Hamiltonian cycles (Q907223): Difference between revisions

Summary: In [C. R. Acad. Sci., Paris 251, 495--497 (1960; Zbl 0091.37503)] \textit{A. Ghouila-Houri} extended Dirac's theorem to directed graphs by proving that if \(D\) is a directed graph on \(n\) vertices with minimum out-degree and in-degree at least \(n/2\), then \(D\) contains a directed Hamiltonian cycle. For directed graphs one may ask for other orientations of a Hamiltonian cycle and in [Ars Comb. 10, 205--209 (1980; Zbl 0448.05034)] \textit{D. D. Grant} initiated the problem of determining minimum degree conditions for a directed graph \(D\) to contain an anti-directed Hamiltonian cycle (an orientation in which consecutive edges alternate direction). We prove that for sufficiently large even \(n\), if \(D\) is a directed graph on \(n\) vertices with minimum out-degree and in-degree at least \(\frac{n}{2}+1\), then \(D\) contains an anti-directed Hamiltonian cycle. In fact, we prove the stronger result that \(\frac{n}{2}\) is sufficient unless \(D\) is one of two counterexamples. This result is sharp.