1
$\begingroup$

Is there a way to find the exact number of Hamiltonian paths in special cases of bipartite graphs, for example, the K(n,n) complete bipartite graph for n ≥ 3?

Thanks.

$\endgroup$
1
$\begingroup$

For $K_{n,n}$, we denote its partitions as $A = \{a_1,...,a_n\}$ and $B = \{b_1,...,b_n\}$. Start from $a_1$, it has $n$ edges. wlog say next point is $b_1$, it will have $n-1$ edges to new vertices. wlog say next point is $a_2$, it will have $n-1$ edges to new vertices. wlog say next point is $b_2$, it will have $n-2$ edges to new vertices. And so on..

So total number of Hamiltonian paths = $n!(n-1)!$.

Using this you will be able to find #Hamiltonian paths for $K_{n,n-1}$ and maybe for regular ones. But in general one can't, since it is NP-Complete.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.