Symmetric graphs, such as the ring, the n-dimensional Boolean hypercube, and the cube-connected cycles, have been widely used as processor/communication interconnection networks. The performance of such networks is often measured through an analysis of their degree, diameter, connectivity, fault tolerance, routing algorithms, etc. In this paper, the authors develop a formal group-theoretic model, called the Cayley graph model, for designing, analyzing, and improving such networks. They show that the model is universal and demonstrate how the networks mentioned above can be represented in the model.
In addition, they show that the model enables the design of new networks based on representations of finite groups. These networks can be analyzed by interpreting the group-theoretic structure. Based on these ideas and other well known combinatorial structures two new classes of networks, the star graphs and the pancake graphs are developed. These are shown to have better performance than the popular n-cubes.