Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652145 | Electronic Notes in Discrete Mathematics | 2013 | 6 Pages |
Abstract
In 1980, Grant initiated the study of minimum degree conditions for a directed graph D to contain an anti-directed Hamiltonian cycle (an orientation in which consecutive edges alternate direction). We prove that for sufficiently large even n, if D is a directed graph on n vertices with minimum out-degree and in-degree at least , then D contains an anti-directed Hamiltonian cycle. This result is sharp.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics