Pancyclic arcs and connectivity in tournaments

A tournament is an orientation of the edges of a complete graph. An arc is pancyclic in a tournament T if it is contained in a cycle of length l , for every 3 ≤  l  ≤ |T|. Let p ( T ) denote the number of pancyclic arcs in a tournament T . In 4, Moon showed that for every non‐trivial strong tournament T , p ( T ) ≥ 3. Actually, he proved a somewhat stronger result: for any non‐trivial strong tournament h ( T ) ≥ 3 where h ( T ) is the maximum number of pancyclic arcs contained in the same hamiltonian cycle of T . Moreover, Moon characterized the tournaments with h ( T ) = 3. All these tournaments are not 2‐strong. In this paper, we investigate relationship between the functions p ( T ) and h ( T ) and the connectivity of the tournament T . Let p k ( n ) := min { p ( T ), T k ‐strong tournament of order n } and h k ( n ) := min{ h ( T ), T k ‐strong tournament of order n }. We conjecture that (for k  ≥ 2) there exists a constant α k > 0 such that p k ( n ) ≥ α k n and h k ( n ) ≥ 2 k +1. In this paper, we establish the later conjecture when k  = 2. We then characterized the tournaments with h ( T ) = 4 and those with p ( T ) = 4. We also prove that for k  ≥ 2, p k ( n ) ≥ 2 k +3. At last, we characterize the tournaments having exactly five pancyclic arcs. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 87–110, 2004