Oriented Hamiltonian Paths in Tournaments: A Proof of Rosenfeld's Conjecture
phan Thomasse · 2000
Tournaments are very rich structures and many questions deal with their subgraphs. In particular, much work has been done concerning oriented paths in tournaments. The first result on this topic, and maybe the very first on tournaments, is Re dei's theorem, which asserts that every tournament contains an odd number of directed hamiltonian paths (and thus at least one). Instead of just looking for directed hamiltonian path, one can seek arbitrary orientations of paths. Such a path may be specified by the signed sequence of the lengths of its blocks, that is, its maximal directed subpaths; the sign of this sequence is + if the first arc of the path is oriented forward and otherwise. In this vein, Gru nbaum proved in [6] that, with three exceptions, every tournament contains an antidirected hamiltonian path (one of type \(1, 1, ..., 1)); the exceptions are the cycle on 3 vertices, the regular tournament on 5 vertices, and the Paley tournament on 7 vertices. A year later, in 1972, Rosenfeld [7] gave an easier proof of a stronger result: in a tournament on at least 9 vertices, each vertex is the origin of an antidirected hamiltonian path. He also made the following conjecture: there is an integer N>7 such that every tournament on n vertices, n N, contains any orientation of the hamiltonian path. The condition N>7 results from Gru nbaum's counterexamples. Several papers gave partial answers to this conjecture: for paths with two blocks (Alspach and Rosenfeld [1], Straight [8]) and for paths having the i th block of length at least doi:10.1006 jctb.1999.1945, available online at http: www.idealibrary.com on