Extremal digraphs on Meyniel-type condition for hamiltonian cycles in
balanced bipartite digraphsArticle
Authors: Ruixia Wang ; Linxin Wu ; Wei Meng
NULL##NULL##NULL
Ruixia Wang;Linxin Wu;Wei Meng
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.
S. Kh. Darbinyan, 2024, On Hamiltonian Cycles in a 2-Strong Digraphs with Large Degrees and Cycles, Pattern Recognition and Image Analysis, 34, 1, pp. 62-73, 10.1134/s105466182401005x.