The number of pancyclic arcs in a k-strong tournament

✍ Scribed by Anders Yeo

• Publisher: John Wiley and Sons
• Year: 2005
• Tongue: English
• Weight: 98 KB
• Volume: 50
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20110

✦ Synopsis

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) ≥ 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