交换折叠交叉立方体的连通度和超连通度

doi:10.13438/j.cnki.jdzk.2019.05.001

吉首大学学报（自然科学版）

• 数学 • 下一篇

交换折叠交叉立方体的连通度和超连通度

蔡学鹏，杨伟，杜洁，任佰通

(新疆农业大学数理学院，新疆乌鲁木齐 830052)

出版日期:2019-09-25 发布日期:2019-11-12

Connectivity and the Super Connectivity of Exchanged Folded Crossed Cubes

CAI Xuepeng, YANG Wei, DU Jie, REN Baitong

(College of Mathematics and Physics, Xinjiang Agricultural University, Urumqi 830052, China)

Online:2019-09-25 Published:2019-11-12
About author:CAI Xuepeng (1991-), male, was born in Wuwei City, Gansu Province, lecturer of College of Mathematics and Physics, Xinjiang Agricultural University, master; reaserch area are graph theory and its application.
Supported by:
National College Students Innovation and Entrepreneurship Training Program of Xinjiang Agricultural University (201810758035)

摘要/Abstract

摘要：

交叉立方体CQn和交换交叉立方体ECQ(s，t)是计算机系统里常用的2个拓扑结构.CQn中系统地移除了一些边后，获得了交换交叉立方体ECQ(s，t).在ECQ(s，t)的基础上增加了一些边，就获得了一个新的互连网络交换折叠交叉立方体EFCQ(s，t).连通度和超连通度是衡量互连网络可靠性和容错性的2个重要参数.证明了EFCQ(s，t)的连通度和超连通度分别等于其最小度和最小边度.

关键词： 交叉立方体, 交换交叉立方体, 交换折叠交叉立方体, 连通度, 超连通度

Abstract:

The crossed cube CQ_n and the exchanged crossed cube ECQ(s, t) are two common topology in the computer system. ECQ(s, t) is obtained by systematically removing links from a binary crossed cube CQ_n. A new interconnection network, named exchanged folded crossed cube EFCQ(s, t), is obtained, which is basically a standard exchanged crossed cube ECQ(s, t) with some extra edges constructed between the nodes. The connectivity and the super connectivity are the two significant factors for measuring the reliability and fault tolerance of the interconnection network. In this work we show that the connectivity of EFCQ(s, t) is equal to its minimum degree, and the super connectivity of EFCQ(s, t) is equal to its minimum edge-degree.

Key words: crossed cube, exchanged crossed cube, exchanged folded crossed cube, connectivity, super connectivity

蔡学鹏，杨伟，杜洁，任佰通. 交换折叠交叉立方体的连通度和超连通度[J]. 吉首大学学报（自然科学版）, DOI: 10.13438/j.cnki.jdzk.2019.05.001.

CAI Xuepeng, YANG Wei, DU Jie, REN Baitong. Connectivity and the Super Connectivity of Exchanged Folded Crossed Cubes[J]. Journal of Jishou University（Natural Sciences Edition), DOI: 10.13438/j.cnki.jdzk.2019.05.001.

参考文献

[1] BONDY J A, MURTY U S R. Graph Theory with Applications[M]. London: MacMillan, 1976: 5-30.
[2] ESFAHANIAN A H, HAKIMI S L. On Computing a Conditional Edge-Connectivity of a Graph[J]. Information Processing Letters, 1988, 27(4): 195-199.
[3] ESFAHANIAN ABDOL-HOSSEIN. Generalized Measures of Fault Tolerance with Application to N-Cube Network[J]. IEEE Transations on Computers, 1989, 38(11): 1 586-1 591.
[4] CAI Xuepeng, ELKIN VUMAR. The Super Connectivity of Folded Crossed Cubes[J]. Information Processing Letters, 2019, 142: 52-56.
[5] MA Meijie, ZHU Liying. The Super Connectivity of Exchanged Hypercubes[J]. Information Processing Letters, 2011, 111(8): 360-364.
[6] MA Meijie, LIU Guizhen, XU Junming. The Super Connectivity of Augmented Cubes[J]. Information Processing Letters, 2008, 106(2): 59-63.
[7] NING Wantao. The Super Connectivity of Exchanged Crossed Cube[J]. Information Processing Letters, 2016, 116(2): 80-84.
[8] WANG Hechao, SHAN Erfang, WANG Wei. On the Super Connectivity of Kro-Necker Products of Graphs[J]. Information Processing Letters, 2012, 112(10): 402-405.
[9] XU Junming, LYU Min, MA Min. Super Connectivity of Line Graphs[J]. Information Processing Letters, 2005, 94(4): 191-195.
[10] XU Junming, XU Min, ZHU Qiang. The Super Connectivity of Shuffle-Cubes[J]. Information Processing Letters, 2005, 96: 123-127.
[11] XU Junming, ZHU Qiang, HOU Xinmin, et al. On Restricted Connectivity and Extra Connectivity of Hypercubes and Folded Hypercubes[J]. Journal Shanghai Jiaotong University, 2005, 10: 203-207.
[12] CHEN Yongchuang, TAN JIMMY J M, HSU LIH-HSING. Super-Connectivity and Super-Edge-Connectivity for Some Interconnection Networks[J]. Applied Mathematics and Computation, 2003, 140: 245-254.
[13] LYU Min, CHEN Guoliang, XU Junming. On Super Edge-Connectivity of Cartesian Product Graphs[J]. Networks, 2007, 49: 135-157.
[14] CHEN Yongchuang, TAN JIMMY J M. Restricted Connectivity for Three Families of Interconnection Networks[J]. Applied Mathematics and Computation, 2007, 188: 1 848-1 855.
[15] LI Xiangjun, XU Junming. Edge-Fault Tolerance of Hypercube-Like Network[J]. Information Processing Letters, 2013, 113(19/20/21): 760-763.
[16] LATIFI SHAHRAM, HEGDE MANJU, NARAGHI-POUR MORT. Conditional Connectivity Measures for Large Multiprocessor Systems[J]. IEEE Transations on Computers, 1994, 43(2): 218-222.
[17] LI Xiangjun, XU Junming. Generalized Measures of Fault Tolerance in Exchanged Hypercubes[J]. Information Processing Letters, 2013, 113(14/15/16): 533-537.
[18] ZHU Qiang, LIU Sanyang, XU Min. On Conditional Diagnosability of the Folded Hypercubes[J]. Information Science, 2008, 178(4): 1 069-1 077.
[19] ZHU Qiang, XU Junming, HOU Xinmin, et al. On Reliability of the Folded Hypercubes[J]. Information Science, 2007, 177(8): 1 782-1 788.
[20] XU Junming. Topological Structure and Analysis of Interconnection Networks[M]. DordrEcht/Boston/London: Kluwer Academic Publishers, 2001: 6-71.
[21] SAAD YOUCEF, SCHULTZ MARTIN H. Topological Properties of Hypercubes[J]. IEEE Transations on Computers, 1988, 37(7): 867-872.
[22] EFE KEMAL, BLACKWELL P K, SLOUGH W, et al. Topological Properties of the Crossed Cube Architecture[J]. Parallel Computing, 1994, 20(12): 1 763-1 775.
[23] KULASINGHE P D. Connectivity of the Crossed Cube[J]. Information Processing Letters, 1997, 61(4): 221-226.
[24] EL-AMAWYA, LATIFI S. Properties and Performance of Folded Hypercubes[J]. IEEE Transations on Parallel and Distributed Systems, 1991, 2(1): 31-42.
[25] LOH PETER, HSU WEN JING, PAN Yi. The Exchanged Hypercube[J]. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(9): 866-874.
[26] QI Heng, LI Yang, LI Keqiu, et al. An Exchanged Folded Hypercube-Based Topology Structure for Interconnection Networks[J]. Concurrency Computation Practice and Experience, 2005, 27(16): 4 194-4 210.
[27] ADHIKARI NIBEDITA, TRIPATHY C R. The Folded Crossed Cube: A New Interconnection Network for Parallel Systems[J]. International Journal of Computer Applications, 2010, 4(3): 43-50.
[28] ZHANG Yanqing. Folded-Crossed Hypercube: A Complete Interconnection Network[J]. Journal of Systems Architecture, 2002, 47(11): 917-922.
[29] LI Keqiu, MU Yuanping, LI Keqin, et al. Exchanged Crossed Cube: A Novel Interconnection Network for Parallel Computation[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(11): 2 211- 2 219.
[30] BHAVANI K, JENA SUDARSON. Exchanged Folded Crossed Cube: A New Interconnection Network for Parallel Systems[J]. Information Processing Letters, 2018, 137: 40-46.
[31] NING Wantao, FENG Xiaoli, WANG Ling. The Connectivity of Exchanged Crossed Cube[J]. Information Processing Letters, 2015, 115(2): 394-396.

交换折叠交叉立方体的连通度和超连通度

Connectivity and the Super Connectivity of Exchanged Folded Crossed Cubes

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价