Hamiltonian Triangulated Toroidal Graphs
by
David W Matula
Southern Methodist University
Coauthors: M Iridon

We describe a family of 6-regular toroidal Hamiltonian decomposable graphs. Algebraically each graph is a rotational Cayley graph defined on the permutation group < 1, k, k² > with k² - k + 1 = 0. The graphs T(i, j) exist for every relativly prime i > j and have i²+ij+j² vertices. There are 18 T(i, j) with less than 100 vertices and asymptotically N/(\surd3 pi) or about .18 N such graphs with at most N vertices. The toroidal embedding has vertex, edge and face symmetry. When i is congruent to j mod 3 T(i, j) is 3-colorable. The Cayley graph parameter k is computable from i, j as a result of the Euclidean algorithm determining a best rational approximation of i/j. The diameter of T(i, j) is the greatest integer in (2i+j)/3. The topological and algebraic structure of these graphs is very rich and they are worthy of furthur study. We also mention applications of these graphs in cellular network studies and in interconnection network architecture.

Date received: May 16, 2001