REPRESENTATIONS AND ROUTING FOR CAYLEY-GRAPHS

In the search for regular, undirected dense graphs for interconnection networks, Chudnovsky et al found certain Cayley graphs that are the densest degree-four graphs known for an interesting range of diameters [1]. However, the group theoretic representation of Cayley graphs makes the development of effective routing algorithms difficult. This paper shows that all finite Cayley graphs can be represented by generalized chordal rings (GCR) and provides a sufficient condition for Cayley graphs to have chordal ring (CR) representations. Once a Cayley graph is represented in the modular integer domain of GCR or CR, existing routing algorithms can be applied. These include a progressive algorithm that finds a shortest path in incremental steps and a recursive algorithm that finds the entire path in a single computation.