×

zbMATH — the first resource for mathematics

Oriented Hamiltonian cycles in tournaments. (English) Zbl 1026.05052
Summary: We prove that every tournament of order \(n\geq 68\) contains every oriented Hamiltonian cycle except possibly the directed one when the tournament is reducible.

MSC:
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bang-Jensen, J.; Gutin, G., Paths, trees and cycles in tournaments, Congr. numer., 115, 131-170, (1996) · Zbl 0894.05032
[2] Benhocine, A.; Wojda, A.P., On the existence of a specified cycle in a tournament, J. graph theory, 17, 469-474, (1983) · Zbl 0522.05027
[3] Bondy, J.A., Basic graph theory: paths and circuits, Handbook of combinatorics, (1995), Elsevier Amsterdam, p. 3-110 · Zbl 0849.05044
[4] Camion, P., Chemins et circuits hamiltoniens des graphes complets, C. R. acad. sci. Paris, 249, 2151-2152, (1959) · Zbl 0092.15801
[5] Grünbaum, B., Antidirected Hamiltonian paths in tournaments, J. combin. theory ser. B, 16, 234-242, (1974) · Zbl 0279.05111
[6] Havet, F., Chemins, cycles et arbres dans LES tournois, (Janvier 1999), Université Claude Bernard Lyon 1, p. 42-99
[7] Havet, F.; Thomassé, S., Oriented Hamiltonian paths in tournaments: a proof of Rosenfeld’s conjecture, J. combin. theory ser. B, 78, 243-273, (2000) · Zbl 1026.05053
[8] Moon, J.W., Topics on tournaments, (1968), Holt, Rinehart, and Winston New York · Zbl 0191.22701
[9] Petrović, V., Antidirected Hamiltonian cicuits in tournaments, Graph theory, novi sad, 1983, (1984), Univ. Novi Sad Novi Sad, p. 259-269
[10] Rosenfeld, M., Antidirected Hamiltonian cycles in tournaments, J. combin. theory ser. B, 16, 234-242, (1974) · Zbl 0279.05111
[11] A. Thomason, Paths and cycles in tournaments, Trans. Amer. Math. Soc.2961986, 167-180. · Zbl 0599.05026
[12] Thomassen, C., Antidirected Hamiltonian cycles and paths in tournaments, Math. ann., 201, 231-238, (1973) · Zbl 0241.05109
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.