Highly Reliable Symmetric Networks

Abstract

In this short paper, we generalize directed loop networks to loop-symmetric networks in which there are N nodes and in which each node has in-degree and out-degree k, subject to the condition that 2<inf>k</inf>does not exceed N. We show that by proper selection of links one can obtain generalized loop networks with optimal or close to optimal diameter and connectivity. The optimized diameter is less than kN1k, where [x] indicates the ceiling of x. We also show that these networks are rather compact in that the diameter is not more than twice the average distance. Roughly 1/2(k−1)N1k nodes can be removed such that the network of remaining nodes is still strongly connected, if all remaining nodes have at least one incoming and one outgoing link left. © 1994 IEEE