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(k,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.