×

zbMATH — the first resource for mathematics

The number of out-pancyclic vertices in a strong tournament. (English) Zbl 1298.05144
Summary: An arc in a tournament \(T\) with \(n\geq 3\) vertices is called pancyclic, if it belongs to a cycle of length \(l\) for all \(3\leq l\leq n\). We call a vertex \(u\) of \(T\) an out-pancyclic vertex of \(T\), if each out-arc of \(u\) is pancyclic in \(T\). T. Yao et al. [Discrete Appl. Math. 99, No. 1–3, 245–249 (2000; Zbl 0939.05045)] proved that every strong tournament contains an out-pancyclic vertex. For strong tournaments with minimum out-degree 1, Yao et al. [loc. cit.] 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.

MSC:
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[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., Each 3-strong tournament contains 3 vertices whose out-arcs are pancyclic, Graphs Combin., 25, 299-307, (2009) · Zbl 1207.05070
[4] Guo, Q.; Li, S.; Guo, Y.; Li, H., Out-arc pancyclicity of vertices in tournaments, Discrete Appl. Math., 158, 996-1005, (2010) · Zbl 1220.05049
[5] Havet, F., Pancyclic arcs and connectivity in tournaments, J. Graph Theory., 47, 87-110, (2004) · Zbl 1060.05037
[6] 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
[7] Thomassen, C., Hamiltonian-connected tournaments, J. Combin. Theory Ser. B., 28, 142-163, (1980) · Zbl 0435.05026
[8] 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
[9] 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.