## Adamus, Janusz and Adamus, Lech and Yeo, Anders - On the Meyniel condition for hamiltonicity in bipartite digraphs

dmtcs:1264 - Discrete Mathematics & Theoretical Computer Science, May 6, 2014, Vol. 16 no. 1 (in progress)
On the Meyniel condition for hamiltonicity in bipartite digraphs

We prove a sharp Meyniel-type criterion for hamiltonicity of a balanced bipartite digraph: For a&#x2265;2, a strongly connected balanced bipartite digraph D on 2a vertices is hamiltonian if d(u)+d(v)&#x2265;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)&#x2265;3a/2.

Source : oai:HAL:hal-01179219v1
Volume: Vol. 16 no. 1 (in progress)
Section: Graph Theory
Published on: May 6, 2014
Submitted on: April 23, 2013
Keywords: Discrete Mathematics, Graph Theory,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]