On Construction of Infinite Families of \(k\)-Tight Optimal Double-Loop Networks

Abstract

A double-loop network (DLN) \(G(N;r,s)\) is a digraph with the vertex set \(V = \{0,1,\ldots, N-1\}\) and the edge set \(E=\{v \to v+r \pmod{N} \text{ and } v \to v+s \pmod{N} | v \in V\}\). Let \(D(N;r,s)\) be the diameter of \(G(N;r,s)\) and let us define \(D(N) = \min\{D(N;r,s) | 1 \leq r < s < N \text{ and } \gcd(N,r,s) = 1\}\), \(D_1(N) = \min\{D(N;1,s) | 1 < s 0\)). Coppersmith proved that there exists an infinite family of \(N\) for which the minimum diameter \(D(N) \geq \sqrt{3N} + c(\log N)^{\frac{1}{4}}\), where \(c\) is a constant.