Skip to Main content Skip to Navigation
Journal articles

On the Meyniel condition for hamiltonicity in bipartite digraphs

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-01179219
Contributor : Hélène Lowinger Connect in order to contact the contributor
Submitted on : Wednesday, July 22, 2015 - 9:15:20 AM
Last modification on : Monday, November 23, 2020 - 12:52:03 PM
Long-term archiving on: : Friday, October 23, 2015 - 10:25:03 AM

File

dmtcs-16-1-17.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Janusz Adamus, Lech Adamus, Anders Yeo. On the Meyniel condition for hamiltonicity in bipartite digraphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (1), pp.293--302. ⟨10.46298/dmtcs.1264⟩. ⟨hal-01179219⟩

Share

Metrics

Record views

56

Files downloads

888