Analysis of interconnection networks based on Cayley graphs related to permutation groups
Jung‐Sing Jwo · 1991
In the past years, various network architectures for the parallel computers have been proposed. Many of these networks can be modeled by simple regular graphs. Among all these proposed networks, hypercube has been recognized as one of the most promising network architecture. Recently, Aker, Harel and Krishnamurthy have introduced a new class of networks, namely star graph. This class of graphs are known as Cayley graphs. The diameter and degree of these graphs are better than those of hypercubes. But these topological properties of a graph are not the only way to measure the goodness of a network. The analysis of node disjoint paths and design of routing table, embeddability, symmetric properties and communication are also important to assess the goodness of a network. In this dissertation, we study the topological properties, embeddability and symmetric properties in star graph and the relatives of star graph--bubble-sort graph and prefix-reversal graph. We propose new network architectures based on complete-transposition graph and alternating-group graph as well. We show that alternating-group graphs exhibit good trade-off between star graph and hypercube from communication and various topological properties. Among all these graphs, it is shown that the relative cycle structure of permutation in complete-transposition graph plays a role quite similar to the Hamming distance in hypercube.