On the Meyniel condition for hamiltonicity in bipartite digraphs
Janusz Adamus, Lech Adamus, Anders Yeo
Abstract
We prove a sharp Meyniel-type criterion for hamiltonicity of a
balanced bipartite digraph: For a≥2, a strongly
connected balanced bipartite digraph D on 2a
vertices is hamiltonian if d(u)+d(v)≥3a whenever
uv∉A(D) and vu∉A(D). As a
consequence, we obtain a sharp sufficient condition for hamiltonicity
in terms of the minimal degree: a strongly connected balanced
bipartite digraph D on 2a vertices is
hamiltonian if δ(D)≥3a/2.
Full Text: PDF PostScript