pith. sign in

arxiv: 1710.07206 · v1 · pith:57Z5KVE2new · submitted 2017-10-19 · 🧮 math.CO

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

classification 🧮 math.CO
keywords hamiltonbipartitecyclesdigraphsdirectedboundscycleevery
0
0 comments X
read the original 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)\geq |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) \geq |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.

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.