×

zbMATH — the first resource for mathematics

Paths and cycles in tournaments. (English) Zbl 0599.05026
Let C denote any orientation of the edges of an n-cycle. The author shows that if \(n\geq 2^{128}\) then every tournament \(T_ n\) contains a copy of every such oriented graph C with the possible exception of the strongly-connected oriented n-cycle; this proves a conjecture of M. Rosenfeld [J. Comb. Theory, Ser. B 16, 234-242 (1974; Zbl 0279.05111)]. The author conjectures that the result is in fact true when \(n\geq 9\).
Reviewer: J.W.Moon

MSC:
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Brian Alspach and Moshe Rosenfeld, Realization of certain generalized paths in tournaments, Discrete Math. 34 (1981), no. 2, 199 – 202. · Zbl 0453.05031 · doi:10.1016/0012-365X(81)90068-6 · doi.org
[2] Abdelhamid Benhocine and A. Paweł Wojda, On the existence of specified cycles in a tournament, J. Graph Theory 7 (1983), no. 4, 469 – 473. · Zbl 0522.05027 · doi:10.1002/jgt.3190070413 · doi.org
[3] Béla Bollobás, Extremal graph theory, London Mathematical Society Monographs, vol. 11, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. · Zbl 0844.05054
[4] Rodney Forcade, Parity of paths and circuits in tournaments, Discrete Math. 6 (1973), 115 – 118. · Zbl 0268.05108 · doi:10.1016/0012-365X(73)90041-1 · doi.org
[5] Branko Grünbaum, Antidirected Hamiltonian paths in tournaments, J. Combinatorial Theory Ser. B 11 (1971), 249 – 257. · Zbl 0198.29304
[6] M.-C. Heydemann, D. Sotteau, and C. Thomassen, Orientations of Hamiltonian cycles in digraphs, Ars Combin. 14 (1982), 3 – 8. · Zbl 0503.05036
[7] K. B. Reid and N. C. Wormald, Embedding oriented \( n\)-trees in tournaments (to appear). · Zbl 0489.05026
[8] M. Rosenfeld, Antidirected Hamiltonian paths in tournaments, J. Combinatorial Theory Ser. B 12 (1972), 93 – 99. · Zbl 0229.05119
[9] M. Rosenfeld, Antidirected Hamiltonian circuits in tournaments, J. Combinatorial Theory Ser. B 16 (1974), 234 – 242. · Zbl 0279.05111
[10] H. Joseph Straight, The existence of certain types of semiwalks in tournaments, Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1980), Vol. II, 1980, pp. 901 – 908. · Zbl 0456.05030
[11] Carsten Thomassen, Antidirected Hamilton circuits and paths in tournaments, Math. Ann. 201 (1973), 231 – 238. · Zbl 0241.05109 · doi:10.1007/BF01427945 · doi.org
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.