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) > ∣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 ∈ B and w ∈ W, where b and w are nonadjacent, we have d(w) + d(b) ≥ |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.