COUNTING HAMILTONIAN PATHS OF TOURNAMENTS
Arthur H. Busch · 2005
It is well known that every tournament has a directed path containing all the vertices of V , i.e. a hamiltonian path. It is an easy exercise to show that a tournament has a unique such path if and only if the arcs of A induce a transitive relation on V. In this paper we show that by reversing the arcs of the hamiltonian path in a transitive tournament with n vertices we obtain a tournament with exactly hn dierent hamiltonian paths, where h0 = h1 = h2 = 1 and for i 3, hi satisfies the tribonacci recurrence; hi = hi 1 + hi 2 + hi 3.