Cycles in kk-traceable oriented graphs

A digraph of order at least kk is termed kk-traceable   if each of its subdigraphs of order kk is traceable. It turns out that several properties of tournaments—i.e., the 2-traceable oriented graphs—extend to kk-traceable oriented graphs for small values of kk. For instance, the authors together with O. Oellermann have recently shown that for k=2,3,4,5,6k=2,3,4,5,6, all kk-traceable oriented graphs are traceable. Moon [J.W. Moon, On subtournaments of a tournament, Canad. Math. Bull. 9(3) (1966) 297–301] observed that every nontrivial strong tournament TT is vertex-pancyclic—i.e., through each vertex there is a cycle of every length from 3 up to the order of TT. The present paper reports results pertaining to various cycle properties of strong kk-traceable oriented graphs and explores the extent to which pancyclicity is retained by strong kk-traceable oriented graphs.For each k≥2k≥2 there are infinitely many kk-traceable oriented graphs—e.g. tournaments. However, we establish an upper bound (linear in kk) on the order of kk-traceable oriented graphs having a strong component with girth greater than 3. As an application of our findings, we show that the Path Partition Conjecture holds for 1-deficient oriented graphs having a strong component with girth at least 6. (A digraph is 1-deficient if its order is exactly one more than the order of its longest paths.)

► We present pancyclicity results for kk-traceable oriented graphs. ► A bound is given on the order of kk-traceable oriented graphs of girth at least 4. ► One case of the Path Partition Conjecture follows as a corollary of our results.