The number of pancyclic arcs contained in a Hamiltonian cycle of a tournament
Bull. Korean Math. Soc. 2014 Vol. 51, No. 6, 1649-1654
https://doi.org/10.4134/BKMS.2014.51.6.1649
Published online November 30, 2014
Michel Surmacs
RWTH Aachen University
Abstract : 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
Full-Text :

   

Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd