Highly reliable symmetric networks
Leendert M. Huisman, S. Kundu · IEEE Transactions on Parallel and Distributed Systems · 1994
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/sup k/ 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 k/spl lsqb/N/sup 1/k//spl rsqb/, where /spl lsqb/x/spl rsqb/ 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/spl minus/1)N/sup 1/k/ 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. >