The Number of Out-Pancyclic Vertices in a Strong Tournament |
| |
Authors: | Qiaoping Guo Shengjia Li Hongwei Li Huiling Zhao |
| |
Institution: | 1. School of Mathematical Sciences, Shanxi University, Taiyuan, 030006, China 2. Institute of Mathematics and Applied Mathematics, Shanxi University, Taiyuan, 030006, China
|
| |
Abstract: | An arc in a tournament T with n ≥ 3 vertices is called pancyclic, if it belongs to a cycle of length l for all 3 ≤ l ≤ n. We call a vertex u of T an out-pancyclic vertex of T, if each out-arc of u is pancyclic in T. Yao et al. (Discrete Appl. Math. 99, 245–249, 2000) proved that every strong tournament contains an out-pancyclic vertex. For strong tournaments with minimum out-degree 1, Yao et al. found an infinite class of strong tournaments, each of which contains exactly one out-pancyclic vertex. In this paper, we prove that every strong tournament with minimum out-degree at least 2 contains three out-pancyclic vertices. Our result is best possible since there is an infinite family of strong tournaments with minimum degree at least 2 and no more than 3 out-pancyclic vertices. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|