Janusz Adamus ; Lech Adamus ; Anders Yeo - On the Meyniel condition for hamiltonicity in bipartite digraphs

dmtcs:1264 - Discrete Mathematics & Theoretical Computer Science, May 6, 2014, Vol. 16 no. 1 - https://doi.org/10.46298/dmtcs.1264
On the Meyniel condition for hamiltonicity in bipartite digraphsArticle

Authors: Janusz Adamus 1,2,3; Lech Adamus 4; Anders Yeo ORCID5

  • 1 Department of Mathematics [London, Ontario]
  • 2 Polska Akademia Nauk = Polish Academy of Sciences
  • 3 Polska Akademia Nauk = Polish Academy of Sciences = Académie polonaise des sciences
  • 4 Faculty of Applied Mathematics [Krakow]
  • 5 Singapore University of Technology and Design

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.


Volume: Vol. 16 no. 1
Section: Graph Theory
Published on: May 6, 2014
Accepted on: July 23, 2015
Submitted on: April 23, 2013
Keywords: Discrete Mathematics, Graph Theory,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

2 Documents citing this article

Consultation statistics

This page has been seen 706 times.
This article's PDF has been downloaded 408 times.