The structure of 4‐strong tournaments containing exactly three out‐arc pancyclic vertices |
| |
Authors: | Qiaoping Guo Shengjia Li Ruijuan Li |
| |
Institution: | 1. School of Mathematical Sciences, Shanxi University, , Taiyuan 030006, P. R. China;2. Institute of Mathematics and Applied Mathematics, Shanxi University, , Taiyuan 030006, P. R. China |
| |
Abstract: | Yao et al. (Discrete Appl Math 99 (2000), 245–249) proved that every strong tournament contains a vertex u such that every out‐arc of u is pancyclic and conjectured that every k‐strong tournament contains k such vertices. At present, it is known that this conjecture is true for k = 1, 2, 3 and not true for k?4. In this article, we obtain a sufficient and necessary condition for a 4‐strong tournament to contain exactly three out‐arc pancyclic vertices, which shows that a 4‐strong tournament contains at least four out‐arc pancyclic vertices except for a given class of tournaments. Furthermore, our proof yields a polynomial algorithm to decide if a 4‐strong tournament has exactly three out‐arc pancyclic vertices. |
| |
Keywords: | tournaments cycles out‐arcs pancyclicity |
|
|