On the Meyniel condition for hamiltonicity in bipartite digraphs

Janusz Adamus, Lech Adamus, Anders Yeo

Research output: Contribution to journalJournal articleResearchpeer-review

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 ∉2 A(D) and vu =2 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.

Original languageEnglish
JournalDiscrete Mathematics and Theoretical Computer Science
Volume16
Issue number1
Pages (from-to)293-302
ISSN1462-7264
Publication statusPublished - 2014
Externally publishedYes

Keywords

  • Bipartite digraph
  • Cycle
  • Cycle factor
  • Degree condition
  • Digraph
  • Hamiltonicity

Fingerprint

Dive into the research topics of 'On the Meyniel condition for hamiltonicity in bipartite digraphs'. Together they form a unique fingerprint.

Cite this