Rotator Graphs: An Efficient Topology for Point-to-Point Multiprocessor Networks

Abstract

Cayley graphs, particularly the Star and Pancake graphs, are receiving attention for use in point-to-point multiprocessor networks. Rotator graphs, a set of directed permutation graphs, are proposed here as an alternative to Star and Pancake graphs. Rotator graphs are defined similarly to the recently proposed Faber-Moore graphs. They have smaller diameter, n — 1 in a graph with n! vertices, than either the Star or Pancake graphs or the k-ary n -cubes. A simple optimal routing algorithm is presented for Rotator graphs. The 77-Rotator graphs are defined as a subset of all Rotator graphs. The distribution of distances of vertices in the n-Rotator graphs is presented, and the average distance between vertices is found. The n-Rotator graphs are shown to be optimally fault tolerant and maximally one-step fault diagnosable. The n-Rotator graphs are shown to be Hamiltonian, and an algorithm for finding a Hamiltonian circuit in the graphs is given. © 1992 IEEE