A Note on the Number of Hamiltonian Paths in Strong Tournaments

Arthur H. Busch

Abstract


We prove that the minimum number of distinct hamiltonian paths in a strong tournament of order $n$ is $5^{{n-1}\over{3}}$. A known construction shows this number is best possible when $n \equiv 1 \hbox{ mod } 3$ and gives similar minimal values for $n$ congruent to $0$ and $2$ modulo $3$.


Full Text: PDF