pith. sign in

arxiv: 1308.0269 · v2 · pith:3YQNQI7Znew · submitted 2013-08-01 · 🧮 math.CO

Semi-degree threshold for anti-directed Hamiltonian cycles

classification 🧮 math.CO
keywords directedsemi-degreecyclehamiltonianminimumthresholdanti-directedgraph
0
0 comments X
read the original abstract

In 1960, Ghouila-Houri extended Dirac's theorem to directed graphs by proving that if D is a directed graph on n vertices with minimum out-degree and in-degree at least n/2 (i.e. minimum semi-degree at least n/2), then D contains a directed Hamiltonian cycle. Of course there are other orientations of a cycle in a directed graph and it is not clear that the semi-degree threshold for the directed Hamiltonian cycle is the same as the semi-degree threshold for some other orientation. In 1980, Grant initiated the problem of determining the minimum semi-degree threshold for the 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 semi-degree at least n/2+1, then D contains an anti-directed Hamiltonian cycle. This result is sharp.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.