增强超立方体的分支连通度

兰州理工大学学报 ›› 2024, Vol. 50 ›› Issue (5): 165-172.

• 数理科学 • 上一篇

增强超立方体的分支连通度

阿斯牙·米吉提^*

喀什大学数学与统计学院, 新疆喀什 844000

收稿日期:2023-01-13 出版日期:2024-10-28 发布日期:2024-10-31
通讯作者: 阿斯牙·米吉提(1994-),女,新疆伽师人,讲师.Email:asiya8079@sina.com
基金资助:
国家自然科学基金(12061039),新疆维吾尔自治区高校基本科研费科研项目(XJEDU2024P065)

The component connectivity of exchanged hypercubes

ASIYA Mijit

College of Mathematics and Statistics, Kashi University, Kashi 844000, China

Received:2023-01-13 Online:2024-10-28 Published:2024-10-31

摘要/Abstract

摘要： 利用r-分支(边)连通度作为可靠性的重要度量,对增强超立方体网络的可靠性进行分析,得到了r-分支(边)连通度,证明了cκ₂(Q_n,k)=cλ₂(Q_n,k)=n+1,其中2≤k≤n－1,cκ₃(Q_n,k)=2n,cλ₃(Q_n,k)=2n+1,其中4≤k≤n－1,cκ₄(Q_n,k)=3n－2,其中4≤k≤n－1,cλ₄(Q_n,k)=3n－1,其中6≤k≤n－1.

关键词: 互联网络, 增强超立方体, 连通度, r-分支(边)连通度

Abstract: The r-component (edge) connectivity is used as an important reliability measure to analyze the reliability of the enhanced hypercube interconnection network, and the r-component (edge) connectivity is obtained. It is proved that cκ₂(Q_n,k)=cλ₂(Q_n,k)=n+1 for 2≤k≤n－1,cκ₃(Q_n,k)=2n,cλ₃(Q_n,k)=2n+1 for 4≤k≤n－1,cκ₄(Q_n,k)=3n－2 for 4≤k≤n－1, cλ₄(Q_n,k)=3n－1 for 6≤k≤n－1.

Key words: interconnection network, enhanced hypercube, connectivity, r-component (edge) connectivity

中图分类号:

O157.5

阿斯牙·米吉提. 增强超立方体的分支连通度[J]. 兰州理工大学学报, 2024, 50(5): 165-172.

ASIYA Mijit. The component connectivity of exchanged hypercubes[J]. Journal of Lanzhou University of Technology, 2024, 50(5): 165-172.

参考文献

[1] KULASINGHE P D.Connectivity of the crossed cube[J].Information Processing Letters,1997,61(4):221-226.
[2] HARARY F.Conditional connectivity[J].Networks,1983,13(3):347-357.
[3] BAUER D,BOESCH F,SUFFFFEL C,et al.Connectivity extremal problems and the design of reliable probabilistic networks[J].The Theory and Applications of Graphs,1981,45-54.
[4] ESFAHANIAN A H.Generalized measures of fault tolerance with application to n-cube networks[J].IEEE Transactions on Computers,1989,38(11):1586-1591.
[5] CHARTRAND G,KAPOOR S F,LESNIAK L,et al.Generalized connectivity in graphs[M].New York:Springer Beriefs in Mathmatics,1984.
[6] SAMPATHKUMAR E.Connectivity of a graph-a generalization[J].J Combin Inform System Sci,1984,9(2):71-78.
[7] HSU L,CHENG E,LIPT K L.Component connectivity of the hypercubes[J].International Journal of Computer Mathematics,2012,89:137-145.
[8] ZHAO S L,YANG W H,ZHANG S R.Component connectivity of hypercubes[J].Theoretical Computer Science,2016,640:115-118.
[9] ZHAO S L,YANG W H.Conditional connectivity of folded hypercubes[J].Discrete Applied Mathematics,2018,257:388-392.
[10] GUO L T.Reliability analysis of twisted cubes[J].Theoretical Computer Science,2018,707:96-101.
[11] ZHAO S L,HAO R X,CHENG E.Two kinds of generalized connectivity of dual cubes[J].Discrete Applied Mathematics,2019,257:306-316.
[12] CHANG J,PAI K J,WU R Y,et al.The 4-component connectivity of alternating group networks[J].Theoretical Computer Science,2019,766:38-45.
[13] CHENG E,KE Q,SHEN Z.Structural properties of generalized exchanged hypercubes generalized exchanged hypercube[J].Emergent Computation,2017,24:215-232.
[14] SHANG H,SABIR E,MENG J X,et al.Characterizations of optimal component cuts of locally twisted cubes[J].Bulletin of the Malaysian Mathematical Sciences Society,2020,43(3):2087-2103.
[15] CHENG E,QIU K E,SHEN Z.Connectivity results of complete cubic networks as associated with linearly many faults[J].Journal of Interconnection Networks,2014,15(1/2):1550007.
[16] TZENG N F,WEI S.Enhanced hypercubes[J].IEEE Trans Comput,1991,40:284-294.
[17] WANG D.Diagnosability of enhanced hypercube[J].IEEE Trans Comput,1994,43(3):1054-1061.
[18] WANG D.Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model[J].IEEE Trans Comput,1999,48:1369-1374.
[19] YANG J S,CHANG J M,PAI K J,et al.Parallel construction of independent spanning trees on enhanced hypercubes[J].IEEE Trans Parallel Distrib Syst,2015,26(11):3090-3098.
[20] CHANG C H,LIN C K,TAN J M,et al.The super spanning connectivity and super spanning laceability of enhanced hypercubes[J].J Supercomput,2009,48(1):66-87.
[21] LIU M,LIU H.Paths and cycles embedding on faulty enhanced hypercube networks[J].Acta Mathematica Scientia,2013,33(1):227-246.
[22] LIU M,LIU H.Cycles in conditional faulty enhanced hypercube networks[J].J Commun Networks,2012,14(2):213-221.
[23] LIU Q,LIU H,QIN R.Paths in enhanced hypercube with a large number of faulty nodes[J].International Journal of Applied Mathematics and Stats,2013,51(21):43-51.
[24] QIN R,LIU H.A further result on cycles in conditional faulty enhanced hypercubes[J].International Journal of Applied Mathematics and Stats,2014,52(2):49-54.
[25] XU J M.Theory and application of graphs[M].Dordrecht:Kluwer Academic Publishers,2003.
[26] YANG X.Fault tolerance of hypercube with forbidden faulty sets[C].北京:信息科技,2003.
[27] YANG X,EVANS D J,CHEN B,et al.On the maximal connected component of hypercube with faulty vertices[J].Int J Comp Math,2004,81(5):515-525.
[28] XU J,ZHU Q,HOU X,et al.On restricted connectivity and extra connectivity of hypercubes and folded hypercubes[J].J Shanghai Jiaotong Univ Sci,2005,10(2):203-207.
[29] GUO L.Reliability analysis of hypercube networks and folded hypercube networks[J].World Scientific and Engineering Academy and Society,2017,16:331-338.
[30] HSU L,CHENG E,LIPTAK L,et al.Component connectivity of the hypercubes[J].Int J Comput Math,2012,89:137-145.
[31] SABIR E,MAMUT A,VUMAR E.The extra connectivity of the enhanced hypercubes[J].Theoretical Computer Science,2017,799(C):22-31.
[32] YUAN D,LIU H M.A structural property of enhanced hypercube[C].Dalian:SPIE Digital Library,2015:345-348.
[33] YU H,YANG J,LIN L,et al.{1,2,3}-restricted connectivity of (n,k)-enhanced hypercubes[J].The Computer Journal,2020,63(9):1355-1371.

增强超立方体的分支连通度

The component connectivity of exchanged hypercubes

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

本文评价

[1]	王同昕, 杨超, 姚兵. 一些特殊图的中间图的2-距离和可区别全染色[J]. 兰州理工大学学报, 2024, 50(3): 156-161.
[2]	卢鹏丽, 薛小燕. 图的一种加权邻接矩阵谱半径和能量的界[J]. 兰州理工大学学报, 2023, 49(1): 144-151.
[3]	卢鹏丽, 钟雨. 图的广义距离特征值[J]. 兰州理工大学学报, 2022, 48(5): 148-152.
[4]	卢鹏丽, 栾睿, 刘文智. 剖分图的联图的距离矩阵相关谱[J]. 兰州理工大学学报, 2022, 48(3): 154-162.
[5]	罗美金, 卢钰松, 韦玉程. 一类含有两个(n－1)-圈的三色有向图本原指数[J]. 兰州理工大学学报, 2022, 48(1): 150-155.
[6]	卢鹏丽, 薛玉龙. 基于拉普拉斯度的k-均匀超图的图熵极值[J]. 兰州理工大学学报, 2021, 47(3): 150-155.
[7]	李永艳, 杜静. 若干Mycielski图的邻点扩展和可区别全染色[J]. 兰州理工大学学报, 2021, 47(3): 170-172.