Bulletin of the
Korean Mathematical Society
BKMS

ISSN(Print) 1015-8634 ISSN(Online) 2234-3016

Article

HOME ALL ARTICLES View

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.

The number of pancyclic arcs contained in a Hamiltonian cycle of a tournament

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

Stats or Metrics

Share this article on :

Related articles in BKMS

more +