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

Let D be a strong balanced digraph on 2a vertices. Adamus et al. have proved that D is hamiltonian if d (u) + d(v) ≥ 3a whenever uv ∉A(D) and vu ∉ A(D). The lower bound 3a is tight. In this paper, we shall show that the extremal digraph on this condition is two classes of digraphs that can be clearl...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2021-07, Vol.23 (3), p.1-12
Main Authors: Wang, Ruixia, Wu, Linxin, Meng, Wei
Format: Article
Language:English
Subjects:
Apexes
Graph theory
Lower bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let D be a strong balanced digraph on 2a vertices. Adamus et al. have proved that D is hamiltonian if d (u) + d(v) ≥ 3a whenever uv ∉A(D) and vu ∉ A(D). The lower bound 3a is tight. In this paper, we shall show that the extremal digraph on this condition is two classes of digraphs that can be clearly characterized. Moreover, we also show that if d(u) + d(v) ≥ 3a - 1 whenever uv ∉ A(D) and vu ∉ A(D), then D is traceable. The lower bound 3a - 1 is tight.
ISSN:1365-8050