Pancyclic arcs and connectivity in tournaments

✍ Scribed by F. Havet

• Publisher: John Wiley and Sons
• Year: 2004
• Tongue: English
• Weight: 226 KB
• Volume: 47
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20018

✦ Synopsis

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