About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IEEE TPDS
Paper
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