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 <>
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

  • HAL Id : hal-01179219, version 1

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 (in progress) (1), pp.293--302. ⟨hal-01179219⟩

Share

Metrics

Record views

184

Files downloads

1246