Premium
Pancyclic arcs and connectivity in tournaments
Author(s) -
Havet F.
Publication year - 2004
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20018
Subject(s) - tournament , combinatorics , conjecture , mathematics , graph , order (exchange) , discrete mathematics , economics , finance
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