zbMATH — the first resource for mathematics

Each 3-strong tournament contains 3 vertices whose out-arcs are pancyclic. (English) Zbl 1207.05070
Summary: An arc in a tournament \(T\) with \(n \geq 3\) vertices is called pancyclic, if it is in a cycle of length \(k\) for all \(3 \leq k \leq n\). A. Yeo [“The number of pancyclic arcs in a k-strong tournament,” J. Graph Theory 50, No. 3, 212–219 (2005; Zbl 1081.05041)] proved that every 3-strong tournament contains two distinct vertices whose all out-arcs are pancyclic, and conjectured that each 2-strong tournament contains 3 such vertices. In this paper, we confirm Yeo’s conjecture for 3-strong tournaments.

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
Full Text: DOI
[1] Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications. Springer, London (2000) · Zbl 0958.05002
[2] Camion, P.: Chemins et circuits hamiltoniens des graphes complets. C. R. Acad. Sci. Paris 249, 2151–2152 (1959) · Zbl 0092.15801
[3] Feng, J., Li, S., Li, R.: An s-strong tournament with s 3 has s + 1 vertices whose out-arcs are 4-pancyclic. Discrete Appl. Math. 154, 2609–2612 (2006) · Zbl 1112.05047
[4] Goldberg, M., Moon, J.W.: Cycles in k-strong tournaments. Pacific J. Math. 40, 89–96 (1972) · Zbl 0207.23003
[5] Li, R., Li, S., Feng, J.: The number of vertices whose out-arcs are pancyclic in a 2-strong tournament. Discrete Appl. Math. 156, 88–92 (2008) · Zbl 1126.05053
[6] Thomassen, C.: Hamiltonian-connected tournaments. J. Combin. Theory Ser. B 28, 142–163 (1980) · Zbl 0435.05026
[7] Yao, T., Guo, Y., Zhang, K.: Pancyclic out-arcs of a vertex in a tournament. Discrete Appl. Math. 99, 245–249 (2000) · Zbl 0939.05045
[8] Yeo, A.: The number of pancyclic arcs in a k-strong tournament. J. Graph Theory 50, 212–219 (2005) · Zbl 1081.05041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.