Pancyclic arcs and connectivity in tournaments

Abstract 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 pk(n) := min {p(T), T k‐strong tournament of order n} and hk(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 pk(n) ≥ αkn and hk(n) ≥ 2k+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, pk(n) ≥ 2k+3. At last, we characterize the tournaments having exactly five pancyclic arcs. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 87–110, 2004