Menu
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} \).