[next] [prev] [up] Date: Sat, 24 Feb 96 00:25:00 -0500
[next] [prev] [up] From: Mark Longridge <mark.longridge@canrem.com >
~~~ ~~~ [up] Subject: Hamiltonian Circuits

Mike wrote:
> there's a general graph theory conjecture that cayley graphs are
> hamiltonian (i.e. have hamiltonian circuits).
> if we take the cayley graph formed by generators
> {F, F', L, L' U, U', R, R', B, B', D, D'}, the conjecture asserts
> that there is a sequence of N quarter turns that visits every
> position exactly once and returns to START.
> (here N = 43252003274489856000 is the order of the group.)

Here's an easy example:

Hamiltonian Circuit for < u2, r2 >
12 elements, 12 moves in group to reach each element

     /    \
1.  u2    r2  12.
    |      |
2.  r2    u2  11.
    |      |
3.  u2    r2  10.
    |      |
4.  r2    u2  9.
    |      |
5.  u2    r2  8.
    |      |
6.  r2    u2  7.
     \   /

Position at 6. is the antipode
Position at 12. is the identity

Also, I seem to remember that the slice-squared group had 8 elements,
and if you graphed a route through the elements it formed a cube.
After drawing such a graph it is not hard to find a hamiltonian
circuit (using the edges of the cube as a pathway).

This may be true in general for all the platonic solids.
(I need to re-check "Regular Polytopes" by Coxeter).

So we have 2 examples and no counter-examples of the general graph
theory Mike mentions.

-> Mark <-

[next] [prev] [up] [top] [help]