Improved Sufficient Conditions for the Existence of Anti-Directed Hamiltonian Cycles in Digraphs

Let D be a directed graph of order n. An anti-directed (hamiltonian) cycle H in D is a (hamiltonian) cycle in the graph underlying D such that no pair of consecutive arcs in H form a directed path in D. In this paper we give sufficient conditions for the existence of anti-directed hamiltonian cycles. Specifically, we prove that a directed graph D of even order n with minimum indegree and outdegree greater than ${frac{1}{2}n + 7sqrt{n}/3}$ contains an anti-directed hamiltonian cycle. In addition, we show that D contains anti-directed cycles of all possible (even) lengths when n is sufficiently large and has minimum in- and out-degree at least ${(1/2+ epsilon)n}$ for any ${epsilon > 0}$ .