On Infinite Families of Optimal Double-Loop Networks with Non-Unit Steps

Abstract

Double-loop networks have been widely studied as architecture for local area networks. A double-loop network \(G(N;s_1,s_2)\) is a digraph with \(N\) vertices \(0,1,\ldots,N-1\) and \(2N\) edges of two types:

\(s_1-edge\): \(i \rightarrow i+s_1 \pmod{N}\); \(i=0,1,\ldots,N-1\).

\(s_2-edge\): \(i \rightarrow i+s_2 \pmod{N}\); \(i=0,1,\ldots,N-1\).

for some fixed steps \(1 \leq s_1 < s_2 < N\) with \(\gcd(N,s_1,s_2) = 1\). Let \(D(N;s_1,s_2)\) be the diameter of \(G\) and let us define \(D(N) = \min\{D(N;s_1,s_2) | 1 \leq s_1 < s_2 < N \text{ and } gcd(N,s_1,s_2) = 1\}\), and \(D_1(N) = \min\{D(N;1,s) | 1 < s < N\}\). If \(N\) is a positive integer and \(D(N) < D_1(N)\), then \(N\) is called a non-unit step integer or a nus integer. Xu and Aguild et al. gave some infinite families of 0-tight nus integers with \(D_1(N) – D(N) \geq 1\). In this work, we give a method for finding infinite families of nus integers. As application examples, we give one infinite family of 0-tight nus integers with \(D_1(N) – D(N) \geq 5\), one infinite family of 2-tight nus integers with \(D_1(N) – D(N) \geq 1\) and one infinite family of 3-tight nus integers with \(D_1(N) – D(N) \geq 1\).