Non‐Hamiltonian Cycles in Tournaments

ABSTRACT A cycle is said to be directed if all its arcs have the same direction. Otherwise, it is said to be nondirected. A strong tournament is a tournament containing a directed path from any vertex to any other vertex. A tournament that is not strong is said to be reducible. Rosenfeld conjectured that there exists an integer such that every tournament of order contains any Hamiltonian nondirected cycle. Havet proved this conjecture for and for reducible tournaments for . Finding non‐Hamiltonian cycles seems more simple. Thomason proved that any tournament of order contains any nondirected cycle of order . This implies the existence of cycles of order , in every tournament of order . He said that the result is probably true for . In this paper, we prove the existence of any nondirected cycle of order , in every tournament of order unless five exceptions.