Connectivity and the Super Connectivity of Exchanged Folded Crossed Cubes

doi:10.13438/j.cnki.jdzk.2019.05.001

Abstract

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

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.

References

[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.