Optimal Double-Loop Networks with Non-Unit Steps

• Published in: The Electronic journal of combinatorics 2003-01, Vol.10 (1)
• Main Authors: Aguiló, F., Simó, E., Zaragozá, M.
• Format: Article
• Language: English
• ISSN: 1077-8926; 1077-8926
• DOI: 10.37236/1695

A double-loop digraph $G(N;s_1,s_2)=G(V,E)$ is defined by $V={\bf Z}_N$ and $E=\{(i,i+s_1), (i,i+s_2)|\; i\in V\}$, 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_{\scriptstyle1\leq s_1 < s_2 < N,\atop\scriptstyle\gcd(N,s_1,s_2)=1}D(N;s_1,s_2),\quad D_1(N)=\min_{1 < s < N}D(N;1,s). $$ Some early works about the diameter of these digraphs studied the minimization of $D(N;1,s)$, for a fixed value $N$, with $1 < s < N$. Although the identity $D(N)=D_1(N)$ holds for infinite values of $N$, there are also another infinite set of integers with $D(N) < D_1(N)$. These other integral values of $N$ are called non-unit step integers or nus integers. In this work we give a characterization of nus integers and a method for finding infinite families of nus integers is developed. Also the tight nus integers are classified. As a consequence of these results, some errata and some flaws in the bibliography are corrected.