A quadratic refinement of Jackson's \CE\ condition for Hamilton cycles in digraphs

Abstract

For a digraph $D$, let ${\alpha }_2(D)$ be the largest size of a vertex set no two of whose vertices lie in a common directed $2$-cycle. Let $f_2(a)$ be the least integer $K$ such that every $K$-connected digraph $D$ with ${\alpha }_2(D)\le a$ has a Hamilton cycle. Jackson proved in 1987 that $f_2(a)\le 2^a(a+2)!$, whereas a conjecture of Jackson and Ordaz predicts $f_2(a)\le a+1$. We prove the quadratic bound $f_2(a)\le 12000a^2$. We also prove that $\kappa (H)\ge 6000(\alpha (H)+r)$ guarantees vertex-disjoint paths joining any prescribed $r$ pairs of distinct vertices and covering $V(H)$.

14 pages