Oriented Hamiltonian Paths in Tournaments: A Proof of Rosenfeld's Conjecture

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.

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series B 2000-03, Vol.78 (2), p.243-273
Main Authors: Havet, Frédéric, Thomassé, Stéphan
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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.
ISSN:0095-8956
1096-0902
DOI:10.1006/jctb.1999.1945