Cycles in k-traceable oriented graphs

AbstractA digraph of order at least k is termed k-traceable if each of its subdigraphs of order k is traceable. It turns out that several properties of tournaments—i.e., the 2-traceable oriented graphs—extend to k-traceable oriented graphs for small values of k. For instance, the authors together with O. Oellermann have recently shown that for k=2,3,4,5,6, all k-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 T is vertex-pancyclic—i.e., through each vertex there is a cycle of every length from 3 up to the order of T. The present paper reports results pertaining to various cycle properties of strong k-traceable oriented graphs and explores the extent to which pancyclicity is retained by strong k-traceable oriented graphs.For each k≥2 there are infinitely many k-traceable oriented graphs—e.g. tournaments. However, we establish an upper bound (linear in k) on the order of k-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.