Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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] –  G. Paseman Aug 5 '10 at 20:37
    
@Gerhard: Ach! You are right. I was counting Hamiltonian paths. Corrected now above. Thanks! –  Joseph O'Rourke Aug 5 '10 at 22:39
    
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] –  G. Paseman Aug 5 '10 at 23:13
    
@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! –  Joseph O'Rourke Aug 6 '10 at 1:41

2 Answers 2

up vote 1 down vote accepted

There are 17 Hamiltonian Circuits on an icosahedron which have a unique shape. You have to find a description of the circuit that codes the this shape. I coded the succession of turnings that the circuit takes at every vertex. On an icosahedron the circuit has one of the four possible continuations, say A, B, C, D. You find a description of the Hamiltonian cycles as lists of ABCD. Then you can easily find the unique ones (remember that each vertex can be the beginning one).

I programmed this in Mathematica.

Later I found, that A. Sainte-Lague published this already in 1937 in a book called: Avec des Nombres et des Lignes.

By the way: The tetrahedron, the cube and the dodecahedron have one Hamiltonian Circuit (HC), the octahedron has two and the icosahedron 17 !

Lei Willems

share|improve this answer
    
Would it be too much to ask for you to list the 17 circuits in your notation? Thanks! –  Joseph O'Rourke Sep 7 '13 at 14:49
1  
Here is the listing of the 17 Hamiltonian Circuits where A means a turn of 108 degrees B a turn of 36 degrees, C means minus 36 degrees and D is minus 108. DABBCDADABCC, DABBCDBADACC, DABBCCDABBCC, DABBDCADABDB, DABBDCBADADB, DABCDADABCDA, CABCDBACDABD, CABDACDBACBD, CABDBDACACDB, DABBCDBBADBC, DABBDBABBBDB, DABBDCBACDAC, CABCBDCABCBD, CABCDADABDAD, CABCDBADADAD, CABDADCABDAD, CABDCABDCABD. I hope I made no typing errors –  user93483 Sep 12 '13 at 15:24

There is a listing of a hamilton cycle count of 2560 at this website: http://mathworld.wolfram.com/IcosahedralGraph.html.

share|improve this answer
    
Thanks for that link, Kristal! I wonder if the 2560 are distinct in my sense? Still, this is a start. Surprising (to me) that there are so many! –  Joseph O'Rourke Aug 5 '10 at 19:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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