Monday, 25 February 2008

graph theory - Why are there 1024 Hamiltonian cycles on an icosahedron?

Fix one edge $e$ of the graph (1-skeleton) of an icosahedron.
By a computer search, I found that there are 1024 Hamiltonian cycles that include $e$.
[But see edit below re directed vs. undirected!]
With the two endpoints of $e$ fixed, there are 10 "free" vertices in the cycle.
Because $1024=2^{10}$, it makes me wonder if there might be a combinatorial viewpoint that
makes it evident that there are 1024 cycles including a fixed edge.
It could just be a numerical coincidence, but if anyone
sees an idea for an argument, I'd appreciate hearing it. Thanks!

icosahedral graph
Incidentally, this MathWorld page says there are 2560 Hamiltonian cycles all together (without
the fixed edge condition). (Thanks to Kristal Cantwell for pointing me to this page.)



Edit. I apologize for misleading! :-/ When I looked at the full output of paths more carefully,
I realize I inadvertently computed directed cycles, so each is represented twice, i.e., both
$$ lbrace 2, 7, 6, 11, 8, 9, 4, 10, 12, 5, 3, 1 rbrace $$
$$ lbrace 1, 3, 5, 12, 10, 4, 9, 8, 11, 6, 7, 2 rbrace $$
are included, etc. So there are 512 undirected cycles, 1024 directed cycles.
The paths are listed here: hpaths.html.

No comments:

Post a Comment