Cycle prefix digraphs for symmetric interconnection networks

• Published in: Networks 1993-10, Vol.23 (7), p.641-649
• Main Authors: Faber, Vance, Moore, James W., Chen, William Y. C.
• Format: Article
• Language: English
• Subjects: Applied sciences; Exact sciences and technology; Flows in networks. Combinatorial problems; Operational research and scientific management; Operational research. Management science
• ISSN: 0028-3045; 1097-0037
• DOI: 10.1002/net.3230230707

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.