Minimal diameter double‐loop networks. I. Large infinite optimal families

Abstract

Abstract Double‐loop networks G(n,h) (also known as circulants) are considered, where each node i in a loop of n nodes is also joined by chords to the nodes i ± h mod n . An integer n , a hop h , and a network G(n,h) are defined as optimal if the diameter D of G(n,h) equals the lower bound k when n is in R [ k ] = {2 k 2 − 2 k + 2, …, 2 k 2 + 2 k + 1}. n ∈ R [ k ], h , and G(n,h) are defined as suboptimal if D = k + 1. New infinite families of optimal networks are identified, along with corresponding optimal hops. For each k , those families contain O (√ k ) values of the 4 k values of n in R [ k ]. Also, lower and upper bounds on optimal and suboptimal hops are given, along with a simple algorithm to compute those hops whenever they exist. It is conjectured that all values of n are either optimal or suboptimal. The optimal graphs G(n,h) are applicable in the design of ILLIAC‐type interconnection networks for parallel processing and of local area communication networks with minimal transmission delay.