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).
Join Matchmaticians Affiliate Marketing
Program to earn up to a 50% commission on every question that your affiliated users ask or answer.
- unanswered
- 112 views
- $5.00
Related Questions
- Rouche’s Theorem applied to the complex valued function $f(z) = z^6 + \cos z$
- Advanced Modeling Scenario
- Explain what the problem means in laymens terms.
- Two exercises in complex analysis
- Complex Integral
- Evaluate $\frac{1}{2 \pi i}\int_{|x|=1} \frac{z^{11}}{12z^{12}-4z^9+2z^6-4z^3+1}dz$
- Derivative Hadamard Product
- A complex Analysis problem
Low bounty for such a high level question.