A degree condition for cycles of maximum length in bipartite digraphs
arXiv:1101.4973 · doi:10.1016/j.disc.2011.11.032
Abstract
We prove a sharp Ore-type criterion for hamiltonicity of balanced bipartite digraphs: A bipartite digraph D, with colour classes of cardinality N, is hamiltonian if, for every pair of vertices u and v from opposite colour classes of D such that the arc uv is not in D, the sum of the outdegree of u and the indegree of v is greater than or equal to N+2.
8 pages, minor exposition changes
Cited by in corpus (4)
- A sufficient condition for a balanced bipartite digraph to be hamiltonian
- Extremal digraphs on Meyniel-type condition for hamiltonian cycles in balanced bipartite digraphs
- A new sufficient condition for a 2-strong digraph to be Hamiltonian
- On the Meyniel condition for hamiltonicity in bipartite digraphs