Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. On the Meyniel condi ...
Article

On the Meyniel condition for hamiltonicity in bipartite digraphs

Janusz Adamus (1) (2) (3), Lech Adamus (4), Anders Yeo ORCID (5)
(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
Download article
Open on HAL
Imported on
April 22, 2013
Published on
May 5, 2014
Last modified on
March 31, 2025
Volume 16
vol. 16:1
Graph Theory
DOI
10.46298/dmtcs.1264
License
https://about.hal.science/hal-authorisation-v1
Natural Sciences and Engineering Research Council of Canada
Indicators
1304
Views
1033
Downloads

On the Meyniel condition for hamiltonicity in bipartite digraphs

Janusz Adamus (1) (2) (3), Lech Adamus (4), Anders Yeo ORCID (5)
(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
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Discrete Mathematics
  • Graph Theory
Cited by

Source: OpenCitations

  • Extremal digraphs on Meyniel-type condition for hamiltonian cycles in balanced bipartite digraphs

    Discrete Mathematics & Theoretical Computer Science

    Authors : Ruixia Wang ORCID, Linxin Wu, Wei Meng ORCID

    Journal reference : Volume vol. 23, no. 3, 2022, pp.

    DOI : 10.46298/dmtcs.5851

  • A New Sufficient Condition for a 2-Strong Digraph to Be Hamiltonian

    Proceedings of Computer Science and Information Technologies 2023 Conference

    Authors : Samvel Darbinyan ORCID

    Journal reference : Volume , 2023, pp.

    DOI : 10.51408/csit2023_27

  • A new sufficient condition for a 2-strong digraph to be Hamiltonian

    Discrete Mathematics & Theoretical Computer Science

    Authors : Samvel Kh. Darbinyan ORCID

    Journal reference : Volume vol. 26:2, 2024, pp.

    DOI : 10.46298/dmtcs.11560

  • On Hamiltonian Cycles in a 2-Strong Digraphs with Large Degrees and Cycles

    Pattern Recognition and Image Analysis

    Authors : S. Kh. Darbinyan ORCID

    Journal reference : Volume 34, 2024, pp. 62-73

    DOI : 10.1134/s105466182401005x

  • On a Problem of Wang Concerning the Hamiltonicity of Bipartite Digraphs

    Mathematical Problems of Computer Science

    Authors : Samvel Darbinyan ORCID, Iskandar Karapetyan ORCID

    Journal reference : Volume , 2018, pp. 26-34

    DOI : 10.51408/1963-0003

  • Sufficient conditions for Hamiltonian cycles in bipartite digraphs

    arXiv (Cornell University)

    Authors : Samvel Kh. Darbinyan ORCID

    Journal reference : Volume 258, 2018, pp. 87-96

    DOI : 10.1016/j.dam.2018.11.024
Preview
Loading PDF preview...