Journal or Publication Title:
Date of publication:
Volume:
ISSN:
Additional Information:
Դարբինյան Ս., Կարապետյան Ի., Дарбинян С., Карапетян И.
Title:
On a Problem of Wang Concerning the Hamiltonicity of Bipartite Digraphs
Other title:
Creator:
Samvel Kh. Darbinyan ; Iskandar A. Karapetyan
Subject:
Uncontrolled Keywords:
Digraph ; cycle ; Hamiltonian cycle ; Bipartite balanced digraph ; Perfect matching.
Coverage:
Abstract:
R. Wang (Discrete Mathematics and Theoretical Computer Science, vol. 19(3), 2017) proposed the following problem. Problem. Let D be a strongly connected balanced bipartite directed graph of order 2a≥8. Suppose that d(x)≥ 2a-k, d(y) ≥a+k or d(y)≥2a-k, d(x)≥a+k for every pair of vertices fx; yg with a common out-neighbour, where 2≤k≤a/2. Is D Hamiltonian? In this paper, we prove that if a digraph D satisfies the conditions of this problem, then (i) D contains a cycle factor, (ii) for every vertex x € V (D) there exists a vertex y € V (D) such that x and y have a common out-neighbour.