Cycle prefix digraphs for symmetric interconnection networks

Abstract

Abstract Motivated by the study of large graphs with given degree and diameter, and the recent interest in the design of highly symmetric interconnection networks (e.g., the study of Cayley digraphs), we are led to the search for large vertex symmetric digraphs with given degree and diameter. The main result of this paper is the construction of a new class of vertex symmetric directed graphs, Γ δ (D) (δ ≥ D ) that have degree δ, diameter D , and (δ + 1)δ … (δ – D + 2) vertices. The graphs Γ δ (D) are first found in the notation of Cayley coset digraphs. Then, we discover that they have a very simple representation in terms of sequences like the commonly studied networks such as the hypercube, de Bruijn graphs, and Kautz graphs. Based on the sequence representation, we give a simple shortest‐path routing scheme. We also show that the average distance in our digraph Γ δ (D) is very close to its diameter D . As a consequence, it follows that the natural routing scheme, which is even simpler than the shortest‐path routing, is nearly optimal on an average basis. © 1993 by John Wiley & Sons, Inc.