In 1960 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 1980 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.
@article{10_37236_3610,
author = {Louis DeBiasio and Theodore Molla},
title = {Semi-degree threshold for anti-directed {Hamiltonian} cycles},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {4},
doi = {10.37236/3610},
zbl = {1329.05127},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3610/}
}
TY - JOUR
AU - Louis DeBiasio
AU - Theodore Molla
TI - Semi-degree threshold for anti-directed Hamiltonian cycles
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/3610/
DO - 10.37236/3610
ID - 10_37236_3610
ER -
%0 Journal Article
%A Louis DeBiasio
%A Theodore Molla
%T Semi-degree threshold for anti-directed Hamiltonian cycles
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/3610/
%R 10.37236/3610
%F 10_37236_3610
Louis DeBiasio; Theodore Molla. Semi-degree threshold for anti-directed Hamiltonian cycles. The electronic journal of combinatorics, Tome 22 (2015) no. 4. doi: 10.37236/3610
