The component connectivity of exchanged hypercubes

Abstract

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

CLC Number:

O157.5

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

References

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