Paths and cycles in tournaments
HTML articles powered by AMS MathViewer
- by Andrew Thomason
- Trans. Amer. Math. Soc. 296 (1986), 167-180
- DOI: https://doi.org/10.1090/S0002-9947-1986-0837805-6
- PDF | Request permission
Abstract:
Sufficient conditions are given for the existence of an oriented path with given end vertices in a tournament. As a consequence a conjecture of Rosenfeld is established. This states that if $n$ is large enough, then every non-strongly oriented cycle of order $n$ is contained in every tournament of order $n$.References
- Brian Alspach and Moshe Rosenfeld, Realization of certain generalized paths in tournaments, Discrete Math. 34 (1981), no. 2, 199–202. MR 611433, DOI 10.1016/0012-365X(81)90068-6
- Abdelhamid Benhocine and A. PawełWojda, On the existence of specified cycles in a tournament, J. Graph Theory 7 (1983), no. 4, 469–473. MR 722064, DOI 10.1002/jgt.3190070413
- Béla Bollobás, Extremal graph theory, London Mathematical Society Monographs, vol. 11, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR 506522
- Rodney Forcade, Parity of paths and circuits in tournaments, Discrete Math. 6 (1973), 115–118. MR 319811, DOI 10.1016/0012-365X(73)90041-1
- Branko Grünbaum, Antidirected Hamiltonian paths in tournaments, J. Combinatorial Theory Ser. B 11 (1971), 249–257. MR 291022, DOI 10.1016/0095-8956(71)90035-9
- M.-C. Heydemann, D. Sotteau, and C. Thomassen, Orientations of Hamiltonian cycles in digraphs, Ars Combin. 14 (1982), 3–8. MR 683972 K. B. Reid and N. C. Wormald, Embedding oriented $n$-trees in tournaments (to appear).
- M. Rosenfeld, Antidirected Hamiltonian paths in tournaments, J. Combinatorial Theory Ser. B 12 (1972), 93–99. MR 285452, DOI 10.1016/0095-8956(72)90035-4
- M. Rosenfeld, Antidirected Hamiltonian circuits in tournaments, J. Combinatorial Theory Ser. B 16 (1974), 234–242. MR 340101, DOI 10.1016/0095-8956(74)90069-0
- H. Joseph Straight, The existence of certain types of semiwalks in tournaments, Congr. Numer. 29 (1980), 901–908. MR 608485
- Carsten Thomassen, Antidirected Hamilton circuits and paths in tournaments, Math. Ann. 201 (1973), 231–238. MR 349467, DOI 10.1007/BF01427945
Bibliographic Information
- © Copyright 1986 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 296 (1986), 167-180
- MSC: Primary 05C20; Secondary 05C38
- DOI: https://doi.org/10.1090/S0002-9947-1986-0837805-6
- MathSciNet review: 837805