Enumeration of Labelled and Unlabelled Hamiltonian Cycles in Complete $k$-partite Graphs

Abstract

We enumerate labelled and unlabelled Hamiltonian cycles in complete $n$-partite graphs $K_{d,d,\dots ,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$