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
Reports

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 :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00072210
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

Identifiers

  • HAL Id : inria-00072210, version 1

Collections

Citation

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

Share

Metrics

Record views

194

Files downloads

167