# The minimum number of Hamiltonian paths in a strongly connected tournament of order $n$

For $n\ge3$ let $a(n)$ be the minimum number of Hamiltonian paths in a strong (i.e., strongly connected) tournament 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'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) follows from (II) by induction. For $n\gt4,$ the upper bound (OEIS sequence 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 without result.

• The answer is about $5^{n/3}$. Reference: A note on the number of hamiltonian paths in strong tournaments, Arthur H. Busch. – Fedor Petrov Mar 19 '16 at 19:54
• The link to the freely available paper is combinatorics.org/ojs/index.php/eljc/article/view/v13i1n3. I am surprised such precise results are known. – Gordon Royle Mar 19 '16 at 23:31

## 1 Answer

Arthur H. Busch proved that the answer is about $5^{n/3}$.

• The exact sequence starts 3,5,9,15,25,45,75,125... which is indeed in the OEIS (oeis.org/A005517) but not as "minimum number of hamilton paths in a strongly-connected tournament" but rather as "Smallest label $f(T)$ given to a rooted tree $T$ with $n$ nodes in Matula-Goebel labelling. But I bet they're the same. – Gordon Royle Mar 20 '16 at 14:35