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 $t\leq \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 ( J. Combin. Inform. System Sci., 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 $3\leq t\leq |V(T)|$ and characterizing all tournaments which satisfy $h^t(T)= t$. We also present all tournaments which fulfill $p^t(T)= t$. 

Keywords

Main Subjects

References

[1] B. Alspach, Cycles of each length in regular tournaments, Canad. Math. Bull. 10 (1967), no. 2, 283–286.
[2] R.J. Douglas, Tournaments that admit exactly one hamiltonian circuit, Proc. London Math. Soc. 21 (1970), no. 4, 716–730.
[3] F. Havet, Pancyclic arcs and connectivity in tournaments, J. Graph Theory 47 (2004), no. 2, 87–110.
[4] J.W. Moon, On k-cyclic and pancyclic arcs in strong tournaments, J. Combin. Inform. System Sci. 19 (1994), 207–214.
[5] C. Thomassen, Hamiltonian-connected tournaments, J. Combin. Theory Ser. B 28 (1980), no. 2, 142–163.
[6] A. Yeo, The number of pancyclic arcs in ak-strong tournament, J. Graph Theory 50 (2005), no. 3, 212–219.
Communications in Combinatorics and Optimization
Volume 4, Issue 2
Special issue in honour of Prof. Lutz Volkmann
December 2019
Pages 123-130

Files

Share

How to cite

Statistics