HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Pancyclic arcs and connectivity in tournaments

Frédéric Havet 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A tournament is an orientation of the edges of a complete graph. An arc is pancyclic in a digraph D if it is contained in a cycle of length l, for every $3\leq l\leq |D|$. In [4], Moon showed that every strong tournament contains at least three pancyclics arcs and characterized the tournaments with exactly three pancyclic arcs. All these tournaments are not 2-strong. In this paper, we are interested in the minimum number $p_k(n)$ of pancyclic arcs in a k-strong tournament of order n. We conjecture that (for $k\geq 2$) there exists a constant $\alpha_k>0$ such that $p_k(n)\geq \alpha_kn$. After proving that every 2-strong tournament has a hamiltonian cycle containing at least five pancyclic arcs, we deduce that for $k\geq 2$, $p_k(n)\geq 2k+3$. We then characterize the tournaments having exactly four pancyclic arcs and those having exactly five pancyclic arcs.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 8:05:39 PM
Last modification on : Friday, February 4, 2022 - 3:11:37 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:05:00 PM


  • HAL Id : inria-00072210, version 1



Frédéric Havet. Pancyclic arcs and connectivity in tournaments. RR-4378, INRIA. 2002. ⟨inria-00072210⟩



Record views


Files downloads