Open AccessOn a Problem of Wang Concerning the Hamiltonicity of Bipartite Digraphs
Author(s) -
Samvel Kh. Darbinyan,
Iskandar A. Karapetyan
Publication year - 2018
Publication title -
mathematical problems of computer science
Language(s) - English
Resource type - Journals
eISSN - 2738-2788
pISSN - 2579-2784
DOI - 10.51408/1963-0003
Subject(s) - bipartite graph , combinatorics , digraph , hamiltonian path , mathematics , vertex (graph theory) , hamiltonian (control theory) , discrete mathematics , graph , mathematical optimization
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 {x; y}with a common out-neighbour, where 2 • k • a=2. Is D Hamiltonian? In this paper, we prove that if a digraph D satis¯es 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.