t-Pancyclic Arcs in Tournaments

Document Type: Original paper

Authors

1 School of Mathematical Sciences, Shanxi University, 030006 Taiyuan, China

2 Lehrstuhl C fuer Mathematik, RWTH Aachen University, 52056 Aachen, Germany

Abstract

Let $T$ be a non-trivial tournament. An arc is emph{$t$-pancyclic} in $T$, if it is contained in a cycle of length $ell$ for every $tleq ell leq |V(T)|$. Let $p^t(T)$ denote the number of $t$-pancyclic arcs in $T$ and $h^t(T)$ the maximum number of $t$-pancyclic arcs contained in the same Hamiltonian cycle of $T$. Moon ({em J. Combin. Inform. System Sci.}, {bf 19} (1994), 207-214) showed that $h^3(T)geq3$ for any non-trivial strong tournament $T$ and characterized the tournaments with $h^3(T)= 3$. In this paper, we generalize Moon's theorem by showing that $h^t(T)geq t$ for every $3leq tleq |V(T)|$ and characterizing the tournaments with $h^t(T)= t$. We also present all tournaments which fulfill $p^t(T)= t$.

Keywords

Main Subjects