Optimal Double-Loop Networks with Non-Unit Steps
| Autor: | Marisa Zaragozá, Ester Simó, Francesc Aguiló |
|---|---|
| Rok vydání: | 2003 |
| Předmět: |
Discrete mathematics
Strongly regular graph Infinite set Applied Mathematics Characterization (mathematics) Theoretical Computer Science Combinatorics Computational Theory and Mathematics Graph power k-vertex-connected graph Discrete Mathematics and Combinatorics Bound graph Geometry and Topology Graph toughness Unit (ring theory) Mathematics |
| Zdroj: | The Electronic Journal of Combinatorics. 10 |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/1695 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|