
Louis DeBiasio

Theodore Molla
Keywords:
Graph Theory, Hamiltonian Cycles, Directed Graphs
Abstract
In 1960 GhouilaHouri extended Dirac's theorem to directed graphs by proving that if $D$ is a directed graph on $n$ vertices with minimum outdegree and indegree 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 antidirected 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 outdegree and indegree at least $\frac{n}{2}+1$, then $D$ contains an antidirected 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.