The class of hypercubes is one of the most important and popular topologies for interconnection networks of multicomputer systems. This class includes the binary hypercube and generalized hypercube. Based on the observation that these two graphs can be constructed using a graph theoretic operation known as the product of graphs, we propose a new method for generating large symmetric graphs for networks of multicomputer systems. This method is essentially algebraic in nature, and makes use of the product of a class of graphs known as quasi-group graphs. We call the graphs we obtain PQG graphs. Because these graphs are constructed by an algebraic operation, it simplifies the analysis of their performance. Many of the well-known topologies can in fact be expressed as PQG graphs; this makes the method a very general one. We also investigate the problem of routing in a PQG graph, and propose a hardware implementation of the routing algorithm to reduce the delay in the routing of messages. We then apply our results to the Petersen graph and show that the product of such graphs has vastly superior topological properties than hypercubes of the same degree.
