1
$\begingroup$

I am seeking a listing of the distinct Hamiltonian cycles following the edges of the icosahedron and the dodecahedron. By distinct I mean they are not congruent by some symmetry of the icosahedron or dodecahedron (respectively). So they do not make the same sequence of angular turns. For example (as Gerhard corrected me in the comments), there is just one distinct Hamiltonian cycle on the cube.

Hamiltonian cycles of the Platonic solids are all over the web, but I am not finding a definitive list of the number and a description of each. Thanks to anyone who can point me in the right direction!

  • 0
    Perhaps I do not understand what you mean by distinct. I think there is only one such cycle on the edges of the cube. [signature removed by moderator]2010-08-05
  • 0
    @Gerhard: Ach! You are right. I was counting Hamiltonian *paths*. Corrected now above. Thanks!2010-08-05
  • 0
    Good. Here is an observation for certain (transitive?) 3-regular graphs. You can pick an arbitrary vertex and two edges from that vertex as a necessary part (from transitivity) of any hamiltonian cycle. The nonselected edge has another vertex which determines two other edges in the cycle. Call this collection of 4 edges a "widget". Now there are only so many ways to place two such widgets on a dodecahedron. You are then well on your way to enumerating all the distinct hamiltonian cycles. [signature removed by moderator]2010-08-05
  • 0
    @Gerhard: Yes, I may just have to implement this myself. I have code that finds *all* Hamiltonian cycles in a graph, but the hard part is winnowing out the congruent duplicates. Something along the lines of your suggestion may be the way to go. Thanks for the idea!2010-08-06

3 Answers 3