The construction of infinite families of any k-tight optimal and singular k-tight optimal directed double loop networks

摘要

The double loop network (DLN) is a circulant digraph with n nodes and outdegree 2. It is an important topological structure of computer interconnection networks and has been widely used in the designing of local area networks and distributed systems. Given the number n of nodes, how to construct a DLN which has minimum diameter? This problem has attracted great attention. A related and longtime unsolved problem is: for any given non-negative integer k, is there an infinite family of k-tight optimal DLN? In this paper, two main results are obtained: (1) for any k ≥ 0, the infinite families of k-tight optimal DLN can be constructed, where the number n(fc, e, c) of their nodes is a polynomial of degree 2 in e with integral coefficients containing a parameter c. (2) for any k ≥ 0, an infinite family of singular k-tight optimal DLN can be constructed.