5
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ The answer is about $5^{n/3}$. Reference: A note on the number of hamiltonian paths in strong tournaments, Arthur H. Busch. $\endgroup$ – Fedor Petrov Mar 19 '16 at 19:54
  • 2
    $\begingroup$ 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. $\endgroup$ – Gordon Royle Mar 19 '16 at 23:31
4
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – Gordon Royle Mar 20 '16 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.