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

Autor: Timothy Morris, Arthur H. Busch, Michael S. Jacobson, Michael J. Plantholt, Shailesh K. Tipnis
Rok vydání: 2011
Předmět:
Zdroj: Graphs and Combinatorics. 29:359-364
ISSN: 1435-5914
0911-0119
DOI: 10.1007/s00373-011-1116-0
Popis: 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 + 7\sqrt{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}$$ .
Databáze: OpenAIRE
Externí odkaz: