Bull. Korean Math. Soc. 2014; 51(6): 1649-1654
Printed November 30, 2014
https://doi.org/10.4134/BKMS.2014.51.6.1649
Copyright © The Korean Mathematical Society.
Michel Surmacs
RWTH Aachen University
A tournament $T$ is an orientation of a complete graph and an arc in $T$ is called pancyclic if it is contained in a cycle of length $l$ for all $3 \leq l \leq n$, where $n$ is the cardinality of the vertex set of $T$. In 1994, Moon \cite{Moo94} introduced the graph parameter $h(T)$ as the maximum number of pancyclic arcs contained in the same Hamiltonian cycle of $T$ and showed that $h(T) \geq 3$ for all strong tournaments with $n \geq 3$. Havet \cite{Hav04} later conjectured that $h(T) \geq 2k+1$ for all $k$-strong tournaments and proved the case $k=2$. In 2005, Yeo \cite{Yeo05} gave the lower bound $h(T) \geq \frac{k+5}{2}$ for all $k$-strong tournaments $T$. In this note, we will improve his bound to $h(T) \geq \frac{2k+7}{3}$.
Keywords: tournament, pancyclic arc, Hamiltonian cycle
MSC numbers: 05C20
© 2022. The Korean Mathematical Society. Powered by INFOrang Co., Ltd