Premium
Cycle prefix digraphs for symmetric interconnection networks
Author(s) -
Faber Vance,
Moore James W.,
Chen William Y. C.
Publication year - 1993
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230230707
Subject(s) - de bruijn sequence , combinatorics , mathematics , cayley graph , hypercube , vertex (graph theory) , degree (music) , discrete mathematics , digraph , graph , physics , acoustics
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.