Sufficient conditions for Hamiltonian cycles in bipartite digraphs

الأصل · EN

We prove two sharp sufficient conditions for hamiltonian cycles in balanced bipartite directed graph. Let D be a strongly connected balanced bipartite directed graph of order 2a. Let x,y be distinct vertices in D. {x,y} dominates a vertex z if x→ z and y→ z; in this case, we call the pair {x,y} dominating. (i) If a≥ 4 and max {d(x), d(y)}≥ 2a-1 for every dominating pair of vertices {x,y}, then either D is hamiltonian or D is isomorphic to one exceptional digraph of order eight. (ii) If a≥ 5 and d(x)+d(y)≥ 4a-3 for every dominating pair of vertices {x,y}, then D is hamiltonian. The first result improves a theorem of R. Wang (arXiv:1506.07949 [math.CO]), the second result, in particular, establishes a conjecture due to Bang-Jensen, Gutin and Li (J. Graph Theory, 22(2), 1996) for strongly connected balanced bipartite digraphs of order at least ten.