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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (in progress) (1), pp.293--302
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01179219
Contributeur : Hélène Lowinger <>
Soumis le : mercredi 22 juillet 2015 - 09:15:20
Dernière modification le : jeudi 4 octobre 2018 - 22:12:02
Document(s) archivé(s) le : vendredi 23 octobre 2015 - 10:25:03

Fichier

dmtcs-16-1-17.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

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

Partager

Métriques

Consultations de la notice

113

Téléchargements de fichiers

395