The number of pancyclic arcs in a k-strong tournament

Abstract

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) 2k + 1, which was also stated by Havet. The previously best-known bounds when k 2 were p(T) 2k + 3 and h(T)