Computer Science ›› 2016, Vol. 43 ›› Issue (Z11): 304-307, 319.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



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .