Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Optimal double-loop networks with non-unit steps | Optimal double-loop networks with non-unit steps F. Aguilo E. Simo and M. Zaragoza Dept. de Matemàtica Aplicada IV Universitat Politecnica de Catalunya C . Jordi Girona 1-3 08034 Barcelona Spain. matfag@ Submitted Apr 1 2002 Accepted Dec 19 2002 Published Jan 6 2003 MR Subject Classifications 05C20 05C12 05C85 68M10. Abstract A double-loop digraph G N Si s2 G V E is defined by V ZN and E i i s1 i i s2 i 6 V for some fixed steps 1 S1 s2 N with gcd N s1 s2 1. Let D N s1 s2 be the diameter of G and let us define D N min D N s1 s2 D1 N min D N 1 s . 1 S1 S2 N 1 s N gcd N si S2 1 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 D1 N holds for infinite values of N there are also another infinite set of integers with D N D1 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. Keywords Diameter double-loop network nus integer optimal family L-shaped tile Smith normal form. Work supported by the Ministry of Science and Technology Spain and the European Regional Development Fund ERDF under project TIC-2001 2171 and by the Catalan Research Council under project 2000SGR00079. THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R2 1 1 Notation and preliminary results Double-loop digraphs G G N Si s2 with 1 S1 S2 N and gcd N S1 S2 1 have the vertex set V ZN and the adjacencies are defined by v v Si mod N for v E V and i 1 2. The hops S1 and S2 between vertices are called steps. These kind of digraphs have been widely studied to modelize some local area networks known as double-loop networks DLN. From the metric point of view the minimization of the diameter of G corresponds to
