Optimal double-loop networks with non-unit steps

F. Aguiló ; E. Simó ; M. Zaragozá

The electronic journal of combinatorics, Tome 10 (2003)

Résumé

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.

Détail

DOI : 10.37236/1695

Classification : 05C20, 05C12, 05C85, 68M10
Mots-clés : diameter, double-loop network, optimal family, \(L\)-shaped tile, Smith normal form, non-unit step integers