1
$\begingroup$

According to wolfram, $n$-wheel graphs have $4(n-1)(n-2)$ Hamilton paths in them.

$n$-wheel graph = http://mathworld.wolfram.com/WheelGraph.html http://mathworld.wolfram.com/HamiltonianPath.html here it states that n-wheel graphs have $4(n-1)(n-2)$ Hamilton paths in them.

Does anyone know a good explanation or proof to this statement? I cant seem to understand how they reached this number .

Thanks!

$\endgroup$
2
$\begingroup$

The Mathworld link counts the number of directed Hamiltonian paths. I will count the number of undirected paths, which can each be oriented in two ways. Let the spokes of $W_n$ be the edges incident with the vertex of degree $n-1$ (the hub). Let the rim vertices be the vertices different from the hub.

First count the number of Hamiltonian paths having exactly 1 spoke. There are $n-1$ spokes, and each spoke corresponds to 2 Hamiltonian paths (counterclockwise & clockwise). So there are $2(n-1)$ such paths.

Now consider the number of Hamiltonian paths having 2 spokes. Consider two cases: 1) the rim vertices incident with the spokes are adjacent 2) the rim vertices incident with the spokes are not adjacent. In Case 1, there are $n-1$ ways to choose the spokes, and once the spokes are chosen, the start and end vertices of the path can be chosen in $n-2$ ways, for $(n-1)(n-2)$ paths. In Case 2, there are $\left(\binom{n-1}{2} - (n-1)\right) = \frac{(n-1)(n-4)}{2}$ ways to choose the spokes, and each choice of spokes corresponds to 2 Hamiltonian paths (counterclockwise & clockwise), for $(n-1)(n-4)$ paths.

Thus the total number of undirected Hamiltonian paths is:

$$2(n-1) + (n-1)(n-2) + (n-1)(n-4) = 2(n-1)(n-2)$$

$\endgroup$
0
$\begingroup$

We can exhaust all the paths. Maybe there's a more elegant way, but here goes.

Let $(v_1, v_2, \ldots, v_{n - 1})$ an ordering of the $n - 1$ vertices outside the wheel. That is, $v_iv_{i+1}$ is an edge, modulo $n - 1$. It helps to draw a wheel and label the vertices in a clockwise fashion. Call the center of the wheel $c$.

Let's look at the paths in which $v_1$ is the start and some $v_j$ is the end. If $j = 2$, the Hamiltonian path has to travel the wheel cycle backwards, visiting $c$ after some vertex $v_k$ and coming back on the cycle at $v_{k - 1}$. So the path is of the form $v_1v_{n - 1}v_{n-2} \ldots v_kcv_{k-1} \ldots v_3v_2$. Now, $v_k$ can be any vertex but $v_2$, so there are $n - 2$ such paths.

If $j = n - 1$, the same argument applies, but we travel the cycle forward. So there are also $n- 1$ such paths.

If $j$ is another value, then the "clockwise" path travels to $v_{j - 1}$, then $c$, then $v_{n - 1}$ and then counterclockwise to $v_j$. The only other path does the same but in the reverse order (go to $v_{j - 1}$, $c$, $v_2$ and $v_j$). So that's two of them. Now, $j$ can take up to $n - 4$ values, so that's $2(n - 4)$ such paths.

And finally, if the path starts at $v_1$ and ends at $c$, there are two such paths - those that travel the wheel cycle in the two directions.

In total, there are $2(n - 1) + 2(n - 4) + 2 = 4n -10$ paths that start at $v_1$. In total that's $(4n - 10)(n - 1)$ paths that start at a vertex on a wheel.

If the path starts at $c$ and ends at say $v_1$, then there are two such paths. So $2(n - 1)$ paths start at $c$.

That's it ! We have them all. The grand total of paths is $(4n - 10)(n - 1) + 2(n - 1) = (4n - 8)(n - 1) = 4(n - 2)(n - 1)$.

$\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.