For $n\ge3$ let $a(n)$ be the minimum number of [Hamiltonian paths](https://en.wikipedia.org/wiki/Hamiltonian_path) in a strong (i.e., [strongly connected](https://en.wikipedia.org/wiki/Strongly_connected_component)) [tournament](https://en.wikipedia.org/wiki/Tournament_(graph_theory)) of order $n.$



> 
> Where is $a(n)$ discussed in the literature? Is the exact value known? If not, what nontrivial bounds are known?
> 
> 
> 


**My attempt:** (It is assumed throughout that $n\ge3.$)


**(I)** $a(n)$ is always odd.


This is because of [Rédei](https://en.wikipedia.org/wiki/L%C3%A1szl%C3%B3_R%C3%A9dei)'s theorem, that a tournament has an odd number of Hamiltonian paths.


**(II)** $a(n+1)\ge a(n)+n-1.$


This follows easily from the fact that every strong tournament of order $n+1$ contains a cycle of length $n.$


**(III)** $\lfloor(n-1)^2/2\rfloor+1\le a(n)\le3\cdot2^{n-4}+3.$


These are the **trivial bounds**. The lower bound (which happens to be [OEIS sequence A099392](http://oeis.org/A099392)) follows from **(II)** by induction. For $n\gt4,$ the upper bound ([OEIS sequence A060013](http://oeis.org/A060013)) is achieved by taking the transitive tournament with vertices $v\_1,\dots,v\_n$ and edges $v\_iv\_j\ (i\lt j),$ and reversing the edges $v\_1v\_3$ and $v\_2v\_n.$


**(IV)** $a(3)=3,\ a(4)=5,\ a(5)=9,\ a(6)\in\{13,15\}.$


That's all I know. I already asked [this question on math.stackexchange.com](https://math.stackexchange.com/questions/1688155/minimum-number-of-hamiltonian-paths-in-a-strongly-connected-tournament-on-n-no) without result.



The minimum number of Hamiltonian paths in a strongly connected tournament of order $n$
[Arthur H. Busch](http://www.combinatorics.org/ojs/index.php/eljc/article/view/v13i1n3) proved that the answer is about $5^{n/3}$.


