The number of pancyclic arcs in a k ‐strong tournament

A tournament is a digraph, where there is precisely one arc between every pair of distinct vertices. An arc is pancyclic in a digraph D , if it belongs to a cycle of length l , for all 3 ≤  l  ≤ | V ( D ) |. Let p ( D ) denote the number of pancyclic arcs in a digraph D and let h ( D ) denote the maximum number of pancyclic arcs belonging to the same Hamilton cycle of D . Note that p ( D ) ≥  h ( D ). Moon showed that h ( T ) ≥ 3 for all strong non‐trivial tournaments, T , and Havet showed that h ( T ) ≥ 5 for all 2‐strong tournaments T . We will show that if T is a k ‐strong tournament, with k  ≥ 2, then p ( T )  ≥ 1/2, nk and h ( T ) ≥ ( k  + 5)/2. This solves a conjecture by Havet, stating that there exists a constant α k , such that p ( T ) ≥ α k n , for all k ‐strong tournaments, T , with k  ≥ 2. Furthermore, the second results gives support for the conjecture h ( T ) ≥ 2 k  + 1, which was also stated by Havet. The previously best‐known bounds when k  ≥ 2 were p ( T ) ≥ 2 k  + 3 and h ( T ) ≥ 5. © 2005 Wiley Periodicals, Inc. J Graph Theory