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

作　　者：Bao-xing CHEN~(1+) Xie-bin CHEN~2 Ji-xiang MENG~3 Wen-jun XIAO~4 1 Department of Computer Science,Zhangzhou Teachers College,Zhangzhou 363000,China 2 Department of Mathematics and Information Science,Zhangzhou Teachers College,Zhangzhou 363000,China 3 College of Mathematics & System Science,Xinjiang University,Urumqi 830046,China 4 Department of Computer Science,South China University of Technology,Guangzhou 510641,China 

出　　处：《Science China Mathematics》2007年第7期1055-1064,共10页中国科学：数学（英文版）

基　　金：This work was supported by the Natural Science Foundation of Fujian Province(Grant No.A0510021);Science and Technology Three Projects Foundation of Fujian Province(Grant No.2006F5068)

摘　　要：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.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.

关 键 词：double loop network DIAMETER k-tight optimal singular k-tight optimal 05C12 05C20 05C85 

分 类 号：O233[理学—运筹学与控制论]