On the Dirac-Type Conjecture for Anti-directed Hamiltonian Digraphs

Abstract

Let $D$ be a directed graph. An anti-directed cycle in $D$ is a set of arcs which form a cycle in the underlying graph, but for which no two consecutive arcs form a directed path in $D$; this cycle is called an anti-directed Hamilton cycle if it includes all vertices of $D$. Grant [6] first showed that if $D$ has even order $n$, and each vertex indegree and outdegree in $D$ is a bit more than $\frac{2n}{3}$, then $D$ must contain an anti-directed Hamilton cycle. More recently, Busch et al. [1] lowered the lead coefficient, by showing that there must be an anti-directed Hamilton cycle if all indegrees and outdegrees are greater than $\frac{9n}{16}$, and conjectured that such a cycle must exist if all indegrees and outdegrees are greater than $\frac{n}{2}$. We prove that conjecture holds for all directed graphs of even order less than 20, and are thus able to extend the above result to show that any digraph $D$ of even order $n$ will have an anti-directed Hamilton cycle if all indegrees and outdegrees are greater than $\frac{11n}{20}$.