zbMATH — the first resource for mathematics

Oriented Hamiltonian paths in tournaments: A proof of Rosenfeld’s conjecture. (English) Zbl 1026.05053
Summary: We prove that with three exceptions, every tournament of order \(n\) contains each oriented path of order \(n\). The exceptions are the antidirected paths in the 3-cycle, in the regular tournament on 5 vertices, and in the Paley tournament on 7 vertices.

05C20 Directed graphs (digraphs), tournaments
05C45 Eulerian and Hamiltonian graphs
Full Text: DOI
[1] Alspach, B.; Rosenfeld, M., Realisation of certain generalized paths in tournaments, Discrete math., 34, 199-202, (1981) · Zbl 0453.05031
[2] Bampis, E.; Hell, P.; Manoussakis, Y.; Rosenfeld, M., Finding an antidirected Hamiltonian path starting with a forward arc from a given vertex of a tournament, Combinatorics and computer science (brest, 1995), Lectures notes in computer science, 1120, (1996), Springer Berlin, p. 67-73
[3] Bang-Jensen, J.; Gutin, G., Paths, trees and cycles in tournaments. surveys in graph theory (San Francisco, CA, 1995), Congr. numer., 115, 131-170, (1996) · Zbl 0894.05032
[4] Bondy, J.A., Basic graph theory: paths and circuits, Handbook of combinatorics, (1995), Elsevier Amsterdam, p. 2, 3-110 · Zbl 0849.05044
[5] Forcade, R., Parity of paths and circuits in tournaments, Discrete math., 6, 115-118, (1973) · Zbl 0268.05108
[6] Grünbaum, B., Antidirected Hamiltonian paths in tournaments, J. combin. theory ser., 11, 249-257, (1971) · Zbl 0198.29304
[7] Rosenfeld, M., Antidirected Hamiltonian paths in tournaments, J. combin. theory ser. B, 12, 93-99, (1972) · Zbl 0229.05119
[8] Straight, H.J., The existence of certain type of semi-walks in tournaments, Proceedings, XI southeastern conference on combinatorics, graph theory and computing, cong. numer., 29, 901-908, (1980)
[9] Thomason, A., Paths and cycles in tournaments, Trans. amer. math. soc., 296, 167-180, (1986) · Zbl 0599.05026
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.