Abstract:
We enumerate labelled and unlabelled Hamiltonian cycles in complete $n$-partite graphs $K_{d,d,\ldots,d}$ having exactly $d$ vertices in each part (in other words, Turán graphs $T(nd, n))$. We obtain recurrence relations that allow us to find the exact values $b_{n}^{(d)}$ of such cycles for arbitrary $n$ and $d$.
Key words and phrases:Hamiltonian cycles, Turán graphs, complete $n$-partite graphs, chord diagrams, linear diagrams, labelled and unlabelled enumeration.