Vertex-transitivity and routing for Cayley graphs in GCR representations
K. Wendy Tang, Bruce W. Arden · 1992
Dense, symmetric graphs are good candidates for effective interconnection networks. Cayley graphs, formed by Borel subgroups, are the densest, symmetric graphs known for a range of diameters [1]. Every Cayley graph can be represented with integer node labels by transforming into another existing topology, Generalized Chordal Ring (GCR) [2]. However, generally speaking, GCR graphs are not fully symmetric. In this paper, we provide a framework for the formulation of the complete symmetry (or vertex-transitivity) of Cayley graphs in the integer domain of GCR representations. Successful realization of such formulation offers a simple, iterative routing algorithm that is capable of determining multiple, shortest paths between any source and destination pairs. An example from a Borel Cayley graph is used to illustrate this concept.