Oriented Hamilton Cycles in Oriented Graphs

Summary

We show that, for every ∈ > 0, an oriented graph of order n will contain n-cycles of every orientation provided each vertex has indegree and outdegree at least (5/12 + ∈)n and n > n₀(∈) is sufficiently large.

Introduction

Dirac's theorem states that every graph G with minimum degree δ(G) ≥ |G|/2 has a hamilton cycle. The simplest analogue for digraphs is given by the theorem of Ghouila-Houri. Given a digraph G of order n and a vertex v ∈ G, we denote the outdegree of v by d⁺(v) and the indegree by d⁻(v). We also define d^°(v) to be min{d⁺(v), d⁻(v)}, and δ^°(G) to be min{d^°(v): v ∈ G}. Ghouila-Houri's theorem implies that G contains a directed hamilton cycle if d^°(G)(G) ≥ n/2. Only recently has a constant c < ½ been established such that every oriented graph satisfying δ^°(G) > cn has a directed hamilton cycle; Häggkvist has shown that c = (½ − 2⁻¹⁵) will suffice. He also showed that the condition δ^°(G) > n/3 proposed by Thomassen is inadequate to guarantee a hamilton cycle, and conjectured that δ^°(G) ≥ 3n/8 is sufficient.

When considering hamilton cycles in digraphs there is no reason to stick to directed cycles only; we might ask for any orientation of an n-cycle. For tournaments G, Thomason has shown that G will contain every oriented cycle (except the directed cycle if G is not strong) regardless of the degrees, provided n is large.