The structure of 4-strong tournaments containing exactly three out-arc pancyclic vertices
✍ Scribed by Qiaoping Guo; Shengjia Li; Ruijuan Li
- Publisher
- John Wiley and Sons
- Year
- 2011
- Tongue
- English
- Weight
- 200 KB
- Volume
- 71
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
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.