Directed Hamilton cycles in digraphs and matching alternating Hamilton cycles in bipartite graphs

Abstract

In 1972, Woodall raised the following Ore type condition for directed Hamilton cycles in digraphs: Let $D$ be a digraph. If for every vertex pair $u$ and $v$, where there is no arc from $u$ to $v$, we have $d^{+}u)+d^{-}(v)\ge |D|$, then $D$ has a directed Hamilton cycle. By a correspondence between bipartite graphs and digraphs, the above result is equivalent to the following result of Las Vergnas: Let $G=(B,W)$ be a balanced bipartite graph. If for any $b\in B$ and $w\in W$, where $b$ and $w$ are nonadjacent, we have $d(w)+d(b)\ge |G|/2+1$, then every perfect matching of $G$ is contained in a Hamilton cycle. The lower bounds in both results are tight. In this paper, we reduce both bounds by $1$, and prove that the conclusions still hold, with only a few exceptional cases that can be clearly characterized.

16 pages, 7 figures, published on "Siam Journal on Discrete Mathematics"

References in corpus (1)

• A survey on Hamilton cycles in directed graphs