Triple loop networks with small transmission delay

AbstractThe problem of finding multiloop networks with a fixed number of vertices and small diameter has been widely studied. In this work, we study the triple loop case of the problem by using a geometrical approach which has been already used in the double loop case. Given a fixed number of vertices N, the general problem is to find ‘steps’ s1, s2, …, sd ∈ ZN, such that the diagraph G(N; s1, s2, …, sd), with set of vertices V = ZN and adjacencies given by v → v + si (mod N), i = 1, 2, …, d, has minimum diameter D(N). A related problem is to maximize the number of vertices N(d,D) when the degree d and the diameter D are given. In the double loop case (d = 2) it is known that N(2, D) = ⌈13(D+2)2⌉ − 1. Here, a method based on lattice theory and integral circulant matrices is developed to deal with the triple loop case (d = 3). This method is then applied for constructing three infinite families of triple loop networks with large order for the values of the diameter D ≡ 2, 4, 5(mod 6), showing that N(3, D) ⩾ 227D3 + O(D2). Similar results are also obtained in the more general framework of (triple) commutative-step digraphs