Complexity of counting Hamiltonian cycles in complete n-partite graph

Is cunting the number of Hamiltonian cycles (cycles that visit each vertex exactly once) in complete n-partite graphs #P-complete problem and how to prove it.

In a complete n-partite graph, vertices are divided into n groups, with edges connecting every vertex to all vertices in other groups (but no edges within groups).

  • Savionf Savionf
    +7

    Low bounty for such a high level question.

Join Matchmaticians Affiliate Marketing Program to earn up to a 50% commission on every question that your affiliated users ask or answer.