折叠交叉立方体的2-外边连通度

doi:10.3969/j.issn.0253-2778.2020.02.002

中国科学技术大学学报 ›› 2020, Vol. 50 ›› Issue (2): 94-99.DOI: 10.3969/j.issn.0253-2778.2020.02.002

折叠交叉立方体的2-外边连通度

蔡学鹏，杨伟

新疆农业大学数理学院,新疆乌鲁木齐 830052

收稿日期:2019-06-13 修回日期:2019-07-30 接受日期:2019-07-30 出版日期:2020-02-28 发布日期:2019-07-30

On 2-extra edge connectivity of folded crossed cube

CAI Xuepeng, YANG Wei

Received:2019-06-13 Revised:2019-07-30 Accepted:2019-07-30 Online:2020-02-28 Published:2019-07-30
Contact: CAI Xuepeng
About author:CAI Xuepeng (corresponding author), male, born in 1991, master/lecturer. Research field: Graph theory and its application. E-mail: cxpmaths@163.com
Supported by:
Supported by College Scientific Research Project of Xinjiang (XJEDU2018Y021), National College Students Innovation and Entrepreneurship Training Program (201810758035).

摘要/Abstract

摘要： g-外边连通度是衡量大型互连网络可靠性和容错性的一个重要参数. 设G是连通图且g是非负整数，如果G中存在某种边子集使得G删除这种边子集后得到的图不连通并且每个分支至少有g+1个点, 则所有这种边子集中基数最小的边子集的基数称为图G的g-外边连通度, 记作λg(G). 由定义可知λ0(G)=λ(G)并且λ1(G)是图G的超边连通度. n维折叠交叉立方体FCQn是由交叉立方体CQn增加2n-1条边后所得. 证明了λ2(FCQn)=3n-1, n≥5.

关键词: 交叉立方体, 折叠交叉立方体, g-外边连通度, 互连网络

Abstract: The g-extra edge connectivity is an important parameter in measuring the reliability and fault tolerance of large interconnection networks. Let G be a connected graph and an integer g≥0, the g-extra edge connectivity of G, denoted by λg(G), is the minimum cardinality of a set of edges of G, if it exists, whose deletion disconnects G and leaves each remaining component to have at least g+1 vertices.

Key words: crossed cube, folded crossed cube, g-extra edge connectivity, interconnection network

中图分类号:

O157.5

蔡学鹏，杨伟. 折叠交叉立方体的2-外边连通度[J]. 中国科学技术大学学报, 2020, 50(2): 94-99.

参考文献

［1］
BONDY J A, MURTY U S R. Graph Theory[M]. New York: Springer, 2008.
[2] XU J M. Topological Structure and Analysis of Interconnection Networks[M]. Dordrecht/ Boston/ London: Kluwer Academic Publishers, 2001.
[3] KULASINGHE P D. Connectivity of the crossed cube[J]. Information Processing Letters, 1997,61(4): 221-226.
[4] HARARY F. Conditional connectivity[J]. Networks, 1983,13(3): 347-357.
[5] FBREGA J, FIOL M A. Extraconnectivity of graphs with large girth[J]. Discrete Math, 1994,127(1-3): 163-170.
[6] FBREGA J, FIOL M A. On the extraconnectivity of graphs[J]. Discrete Math, 1996, 155: 49-57.
[7] CAI X P, VUMAR E. The super connectivity of folded crossed cubes[J]. Information Processing Letters, 2019,142: 52-56.
[8] CHEN Y C, TAN J J M, HSU L H. Super-connectivity and super-edge-connectivity for some interconnection networks[J]. Applied Mathematics and Computation, 2003,140(2): 245-254.
[9] GUO L, QIN C, GUO X. Super connectivity of Kronecker products of graphs[J]. Information Processing Letters, 2010,110(16): 659-661.
[10] LV M, CHEN G L, XU J M. On super edge-connectivity of Cartesian product graphs[J]. Networks, 2007,49(2): 135-157.
[11] MA M J, ZHU L Y. The super connectivity of exchanged hypercubes[J]. Information Processing Letters, 2011,111(8): 360-364.
[12] MA M J, LIU G Z, XU J M. The super connectivity of augmented cubes[J]. Information Processing Letters, 2008,106(2): 59-63.
[13] NING W T. The super connectivity of exchanged crossed cube[J]. Information Processing Letters, 2016,116(2): 80-84.
[14] WANG H, SHAN E, WANG W. On the super connectivity of Kronecker products of graphs[J]. Information Processing Letter, 2012, 112: 402-405.
[15] XU J M, ZHU Q, HOU X M, et al. On restricted connectivity and extra connectivity of hypercubes and folded hypercubes[J]. Journal Shanghai Jiaotong University, 2005,10(2): 203-207.
[16] XU J M, LV M, MA M J, et al. Super connectivity of line graphs[J]. Information Processing Letters, 2005, 94(4): 191-195.
[17] XU J M, XU M, ZHU Q. The super connectivity of shuffle-cubes[J]. Information Processing Letters, 2005,96(4): 123-127.
[18] ZHU Q, XU J M, HOU X M, et al. On reliability of the folded hypercubes[J]. Information Science, 2007,177(8): 1782-1788.
[19] ZHOU J X. On g-extra connectivity of hypercube-like networks[J]. Journal of Computer and System Sciences, 2017, 88: 208-219.
[20] ZHANG M M, ZHOU J X. On g-extra connectivity of folded hypercubes[J]. Theoretical Computer Science, 2015,593: 146-153.
[21] GU M M, HAO R X. 3-extra connectivity of 3-ary n-cube networks[J]. Information Processing Letters, 2013,114(9): 146-153.
[22] CHANG N W, TSAI C Y, HSIEH S Y. On 3-extra connectivity and of 3-extra edge connectivity of folded hypercubes[J]. IEEE Transactions on Computers, 2014,63(6): 1594-1600.
[23] WANG S Y,WANG Z H,WANG M J S. The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks[J]. Computer Journal, 2016, 59(12): 1839-1856.
[24] HONG W S, HSIEH S Y. Extra edge connectivity of hypercube-like networks[J]. International Journal of Parallel, Emergent and Distributed Systems,2013,28(2): 123-133.
[25] ZHU Q, XU J M, LV M. Edge fault tolerance analysis of a class of interconnection networks[J]. Applied Mathematics and Computation, 2006, 172(1): 111-121.
[26] LI X, XU J M. Edge-fault tolerance of hypercube-like network[J]. Information Processing Letters, 2013,113: 760-763.
[27] MA S D, MENG J X. On the reliability of double generalized Petersen graph[J]. Journal of Xinjiang University (Natural Science Edition), 2018,35(2): 150-157.
[28] KFE K, BLACKWELL P K, SLOUGH W, et al. Topological properties of the crossed cube architecture[J]. Parallel Computing, 1994, 20(12): 1763-1775.
[29] KFE K. The crossed cube architecture for parallel computation[J]. IEEE Transactions on Parallel and Distributed Systems, 1992, 3(5): 513-524.
[30] CHEN Y Q, TAN J J M. Restricted connectivity for three families of interconnection networks[J]. Applied Mathematics and Computation, 2007, 188: 1848-1855.
[31] ELAMAWY A, LATIFI S. Properties and performance of folded hypercubes[J]. IEEE Transactions on Parallel and Distributed Systems, 1991, 2(1): 31-42.
[32] ADHIKARI N, 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.
[33] ZHANG Y Q. Folded-crossed hypercube:A complete interconnection network[J]. Journal of Systems Architecture, 2002,47(11): 917-922.
[34] PAI K J, CHANG J M, YANG J S. Vertex-transitivity on folded crossed cubes[J]. Information Processing Letters, 2016,116(11): 689-693.

()
()

[1]	李心田, 刘世平. Amply regular图的林-陆-丘曲率和直径[J]. 中国科学技术大学学报, 2021, 51(12): 889-893.
[2]	火清羿. 染色数为5和6的图中的圈长[J]. 中国科学技术大学学报, 2021, 51(5): 374-381.
[3]	蔡改香，梅培林，余桂东. 逆度和图的性质[J]. 中国科学技术大学学报, 2020, 50(6): 852-859.
[4]	剧宏娟，雷英杰. 三圈图和四圈图的最大无符号拉普拉斯分离度[J]. 中国科学技术大学学报, 2020, 50(4): 402-408.
[5]	王礼想，余桂东，徐弈. 图的哈密尔顿连通性和从任意点出发都可迹的充分条件[J]. 中国科学技术大学学报, 2020, 50(2): 100-105.
[6]	鲁学星. 顶点偏序集上的平面序[J]. 中国科学技术大学学报, 2018, 48(11): 902-905.
[7]	梁勇，裴利丹，胡夫涛，侯新民. 笛卡尔乘积和直积图的全{k}控制划分数[J]. 中国科学技术大学学报, 2018, 48(8): 605-611.
[8]	洪振木，福克曼·鲁茨，徐俊明. 有向图是极大连通的和超连通的充分条件[J]. 中国科学技术大学学报, 2018, 48(8): 612-617.

折叠交叉立方体的2-外边连通度

On 2-extra edge connectivity of folded crossed cube

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

本文评价