Path Extendable Tournaments

ABSTRACT A digraph is called path extendable if for every nonhamiltonian (directed) path in , there exists another path with the same initial and terminal vertices as , and for a vertex . Hence, path extendability implies paths of continuous lengths between every vertex pair. In earlier works of C. Thomassen and K. Zhang, it was shown that the condition of small or positive implies paths of continuous lengths between every vertex pair in a tournament , where is the irregularity of and denotes for the minimum number of paths of length 2 from to among all vertex pairs . Motivated by these results, we study sufficient conditions in terms of and that guarantee a tournament is path extendable. We prove that (1) a tournament is path extendable if , and (2) a tournament is path extendable if . As an application, we deduce that almost all random tournaments are path extendable.