DIRECTED HAMILTON CYCLES IN DIGRAPHS AND MATCHING ALTERNATING HAMILTON CYCLES IN BIPARTITE GRAPHS

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) >= vertical bar D vertical bar, 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 is an element of B and w is an element of W, where b and w are nonadjacent, we have d(w) + d(b) >= vertical bar G vertical bar/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.