Connectivity of Imase and Itoh digraphs
- 1 January 1988
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 37 (11) , 1459-1461
- https://doi.org/10.1109/12.8718
Abstract
An important problem in the design of efficient interconnection networks consists of finding digraphs with a minimal diameter for a given number of nodes n and a given degree d. The best family known at present, denoted by G(n,d), has been proposed by Imase and Itoh. Its vertex set is the set of integers modulo n and its arc set A is defined as A=((x,y)/y identical to -dx-a, 1or=aor=d). The authors determine the connectivity of these digraphs, which proves that they are highly reliable. More precisely, we show that provided that the diameter is greater than 4, the connectivity of G(n,d) is d if n=k(d+1) and gcd(n,d)Keywords
This publication has 6 references indexed in Scilit:
- Large fault-tolerant interconnection networksGraphs and Combinatorics, 1989
- Generalized de Bruijn digraphsNetworks, 1988
- Strategies for interconnection networks: Some methods from graph theoryJournal of Parallel and Distributed Computing, 1986
- Connectivity of Regular Directed Graphs with Small DiametersIEEE Transactions on Computers, 1985
- A Design for Directed Graphs with Minimum DiameterIEEE Transactions on Computers, 1983
- Line digraph iterations and the (d,k) problem for directed graphsPublished by Association for Computing Machinery (ACM) ,1983