Computer Science ›› 2016, Vol. 43 ›› Issue (Z11): 304-307.doi: 10.11896/j.issn.1002-137X.2016.11A.071

Previous Articles     Next Articles

Hamiltonian Decomposition of 2r-regular Graph Connected Cycles Networks

SHI Hai-zhong, CHANG Li-ting, ZHAO Yuan, ZHANG Xin and WANG Hai-feng   

  • Online:2018-12-01 Published:2018-12-01

Abstract: An Interconnection network is an important part of a supercomputer.The interconnection network is often modeled as an undirected graph,in which the vertices correspond to processor/communication parts,and the edges correspond to communication channels.In 2010,Hai-zhong Shi proposed the model of 2r-regular graph connected cycles,for designing analyzing and improving such networks,and proposed many conjectures.In this paper,we proved that any 2r-regular graph-connected cycles network is a union of edge-disjoint Hamiltonian cycle and a perfect matching.Therefore,we proved that the conjectures are true when primitive graphs are 2r-regular connected graph.

Key words: Interconnection network,2r-regular connected graph,2r-regular graph-connected cycle network,Hamiltonian cycle,Perfect matching,Conjecture

[1] Akers S B,Harel D,Krishnamurthy B.The star graph:An attractive alternative to the n-cube[C]∥Proceeding of the 1987 International conference on Parallel Processing.The Pennsylvania University Press,1987:393-400
[2] Akers S B,Krishnamurthy B.A group-theoretic model for symmetric interconnection networks[J].IEEE Transactions on Computers,1989,38(4):555-565
[3] Biggs N.Algebraic Graph theory (second edition)[M].Cambridge University Press,1993
[4] Bondy J A,Murty U S R.Graph Theory with Applications[M].Macmillan Press Ltd,London and Basingstoke,1976
[5] Azevedo M M,Bagherzadeh N,Latifi S.Fault-diameter of theStar-connected cycles interconnection network[C]∥Proceeding of the 28th Annual Hawaii International Conference on System Sciences.Vol.II(Software Technology),Maui,Hawaii,1995,469-478
[6] Carlsson G E,Cruthirds J E,Sexton H B,et al.Interconnetion networks based on a generalization of Cube-connected cycles[J].IEEE Transactions on Computers,1985,34(8):769-772
[7] Latifi S,Azevedo M M,Bagherzadeh N.The star connected cycles:A fixed-degree network for parallel processing[C]∥ 1993 International Conference on Parallel(ICPP’93).1993:91-95
[8] Ohring S R,Sarkar F,Hohndel D H.Cayley graph connected cycles:A new class of fixed-degree Interconnection networks[C]∥Proceeding of the 28th Annual Hawaii International Conference on System Science.1995:479-488
[9] Xu Min,Hu Xiao-dong,Zhu Qiang.Edge-biupancyclicity of star graph under edge-fault tolerant[J].Applied Mathematics and Computation,2006,183(2):927-929
[10] 师海忠.互连网络的代数环模型[D].北京:中国科学院应用数学研究所,1998
[11] 高随祥.图论与网络流理论[M].北京:高等教育出版社,2009
[12] 徐俊明.组合网络理论[M].北京:科学出版社,2007
[13] Saad Y,Schltz M H.Topological properties of Hypercubes[J].IEEE Transactions on Computer,1988,37(7):867-872
[14] Efe K.A variation on the hypercube with lower diameter[J].IEEE Transactions on Computer,1991,0(11):1312-1316
[15] Ei-Amawy A,Latifi S.Properties and performance of folded hypercubes[J].IEEE Transactions on Parallel and Distributed Systems,1991,2(1):31-42
[16] Cull P,Larson S M.The MObius Cube[J].IEEE Transactions on Computer,1995,44(5):647-659(下转第319页)(上接第307页)
[17] Efe K.The Crossed cube architecture for parallel computation[J].IEEE Transactions on Parallel and distributed systems,1998,3(5):513-523
[18] Hwang,Briggs F A.Computer architecture and Parallel proces-sing[M].McGrawHill College,1984
[19] Hsu L H,Lin C K.Graph theory and Interconnection networks[M].New York:CRC Press,2009
[20] Bhuyan L N,Agrawal D D.Greneralized hypercube and hyperbus structures for a computer network[J].IEEE Transactions on Computer,1994,33(4):323-333
[21] 师海忠.正则图连通圈:多种互连网络的统一模型[C]∥中国运筹学会第十届学术交流会论文集.北京,2010:202-208
[22] 师海忠,牛攀峰,马继勇,等.互连网络的向量图模型[J].运筹学学报,2011,5(3):115-123
[23] 师海忠,路建波.关于互连网络的几个猜想[J].计算机工程与应用,2008,4(31):112-115
[24] 师海忠.互连网络的新模型:多部群论模型[J].计算机科学,2013,0(9):21-24
[25] 师海忠.几类新的笛卡尔乘积互连网络[J].计算机科学,2013,0(6A):265-270
[26] Shi Hai-zhong,Shi Yue.A new model for interconnection net-work:k-hierarchical ring and r-layer graph network.
[27] Shi Hai-zhong,Shi Yue.A hierarchical ring group-theoreticmodel for interconnection networks.
[28] Shi Hai-zhong,Yue Shi.Cell-breading graph model for interconnection networks.

No related articles found!
Full text



No Suggested Reading articles found!