On a Problem of Wang Concerning the Hamiltonicity of Bipartite Digraphs

Abstract

R. Wang (Discrete Mathematics and Theoretical Computer Science, vol. 19(3), 2017) proposed the following problem. \textbf{Problem.} Let $D$ be a strongly connected balanced bipartite directed graph of order $2a\ge 8$. Suppose that $d(x)\ge 2a-k$, $d(y)\ge a+k$ or $d(y)\ge 2a-k$, $d(x)\ge a+k$ for every pair of vertices $x,y$ with a common out-neighbour, where $2\le k\le 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\in V(D)$ there exists a vertex $y\in V(D)$ such that $x$ and $y$ have a common out-neighbour.

8 pages