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,\dots ,N-1\}$ and the edge set $E=\{v\to v+r(\mathrm{mod}N)\text{ and }v\to v+s(\mathrm{mod}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\le r<s<N\text{ and }gcd(N,r,s)=1\}$, $D_1(N)=min\{D(N;1,s)|1<s0$). Coppersmith proved that there exists an infinite family of $N$ for which the minimum diameter $D(N)\ge \sqrt{3N}+c(\log N{)}^{\frac{1}{4}}$, where $c$ is a constant.