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 cy...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2013-05, Vol.29 (3), p.359-364
Main Authors: Busch, Arthur H., Jacobson, Michael S., Morris, Timothy, Plantholt, Michael J., Tipnis, Shailesh K.
Format: Article
Language:English
Subjects:
Combinatorial analysis
Combinatorics
Engineering Design
Graph theory
Graphs
Mathematics
Mathematics and Statistics
Original Paper
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 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 for any .
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-011-1116-0