A Sufficient Condition for Oriented Graphs to be Hamiltonian

Pan Lin Qiang1, Zhang Ke Min1
1Department of Mathematics, Nanjing University, Nanjing, 210093, P. R. of China

Abstract

In this paper, we prove the following result:
Let \(D\) be a disconnected oriented graph of order \(n\). If
\(d^+(u)+d^+(v) \geq n-2\) for any pair \(u,v\) of nonadjacent vertices such that \(N^+(u) \cap N^+(v) \neq \emptyset\) and \(d^-(u) + d^-(v) \geq n-2\) for any pair \(u,v\) of nonadjacent vertices such that \(N^-(u) \cap N^-(v) \neq \emptyset\), then \(D\) contains a directed Hamiltonian cycle.