Discrete Mathematics & Theoretical Computer Science, Vol 16, No 1 (2014)

Font Size:  Small  Medium  Large

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