On the Meyniel condition for hamiltonicity in bipartite digraphs
Authors: Janusz Adamus 1,2; Lech Adamus 3; Anders Yeo 4
NULL##NULL##0000-0003-0293-8708
Janusz Adamus;Lech Adamus;Anders Yeo
1 Department of Mathematics [London, Ontario]
2 Polska Akademia Nauk = Polish Academy of Sciences
3 Faculty of Applied Mathematics [Krakow]
4 Singapore University of Technology and Design
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.