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 ℓ for every t≤ℓ≤|V(T)|. Let pt(T) denote the number of t-pancyclic arcs in T and ht(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 h3(T)≥3 for any non-trivial strong tournament T and characterized the tournaments with h3(T)=3. In this paper, we generalize Moon's theorem by showing that ht(T)≥t for every 3≤t≤|V(T)| and characterizing all tournaments which satisfy ht(T)=t. We also present all tournaments which fulfill pt(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