Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2008 Research Summary

Combinatorial Searches on Complex Highly Symmetrical Graphs

View Current Project Information

Carlo H. Séquin

Rather complex but highly symmetrical graphs can be derived from the regular polytopes in three, four, or higher dimensions. We have been looking for congruent sets of Hamiltonian cycles on these graphs, i.e., closed-loop paths that visit all the nodes exactly once. We have already found sets of congruent Hamiltonian cycles on these edge-graphs that together cover all the edges of these polytopes in four dimensions.

Now the search has been extended to more generalized symmetrical cycles, for instance, for closed triangle strips on the 4-dimensional 24-Cell and on the 600-Cell that "visit" all the edges exactly once.

Figure 1
Figure 1: Cross-eye stereo image of the two congruent Hamiltonian cycles (shown in fat red cylinders and skinny yellow triangular prisms) on the edges of the 4-dimensional 120-Cell that together cover all 1200 edges