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.

Improve this question
$\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
    Commented Mar 19, 2016 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
    Commented Mar 19, 2016 at 23:31

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\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
    Commented Mar 20, 2016 at 14:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .