Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00261
Finding Hamilton cycles in robustly expanding digraphs
Demetres Christofides, Peter Keevash, Daniela Kühn, and Deryk Osthus
Vol. 16, no. 2, pp. 335-358, 2012. Regular paper.
Abstract We provide an NC algorithm for finding Hamilton cycles in directed graphs with a certain robust expansion property. This property captures several known criteria for the existence of Hamilton cycles in terms of the degree sequence and thus we provide algorithmic proofs of (i) an `oriented' analogue of Dirac's theorem and (ii) an approximate version (for directed graphs) of Chvátal's theorem. Moreover, our main result is used as a tool in a recent paper by Kühn and Osthus, which shows that regular directed graphs of linear degree satisfying the above robust expansion property have a Hamilton decomposition, which in turn has applications to TSP tour domination.
Submitted: February 2009.
Reviewed: April 2012.
Revised: April 2012.
Accepted: April 2012.
Final: May 2012.
Published: May 2012.
Communicated by Sue Whitesides
article (PDF)
BibTeX