Optimal double-loop networks with non-unit steps. (English) Zbl 1017.05043

Electron. J. Comb. 10, Research paper R2, 13 p. (2003); printed version J. Comb. 10, No. 2 (2003).
The paper first defines a double-loop digraph \(G(N; s_1,s_2)\) and its diameter \(D(N; s_1,s_2)\) for some fixed steps \(1\leq s_1< s_2< N\) with \(\text{gcd}(N; s_1, s_2)= 1\). These digraphs are closely related to some local area networks known as double-loop networks. Some early works on the minimization of \(D(N; 1,s)\) for a fixed value \(N\) with \(1< s< N\) were studied. Let \(D(N)\) be the minimum of \(D(N; s_1,s_2)\) with \(1\leq s_1< s_2< N\) and \(\text{gcd}(N; s_1,s_2)= 1\), and let \(D_1(N)\) be the minimum of \(D(N; 1,s)\) 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 integer values of \(N\) are called the non-unit step integers. The paper gives a characterization of these integers and develops a method for finding infinite families of them.


05C20 Directed graphs (digraphs), tournaments
05C12 Distance in graphs
05C85 Graph algorithms (graph-theoretic aspects)
68M10 Network design and communication in computer systems
Full Text: EuDML EMIS