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

The Super Connectivity of Exchanged Folded Hypercubes

作　　者：蔡学鹏 马丽[1] CAI Xue-peng;MA Li(College of Mathematics and Physics,Xinjiang Agricultural University,Urumqi 830052,China)

机构地区：[1]新疆农业大学数理学院,新疆乌鲁木齐830052

出　　处：《安徽师范大学学报（自然科学版）》2020年第3期216-222,共7页Journal of Anhui Normal University(Natural Science)

基　　金：新疆维吾尔自治区高校科研计划项目(XJEDU2018Y021);国家级大学生创新创业训练计划项目(201810758035).

摘　　要：超连通度(超边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数。设G是连通图,图G的超连通度(超边连通度)是指从G中删除最小数目的点(边)使得G不连通,且G的每个连通分支中都至少包含两个顶点。李等人(2015)提出了一个新的网络交换折叠超立方体网络EFH(s,t)。该文利用超连通度和超边连通度作为评价可靠性的重要度量,对交换折叠超立方体网络的可靠性进行分析,得到了交换折叠超立方体网络的超连通度和超边连通度,证明了EFH(s,t)的超连通度和超边连通度等于2s+2,1 s t。这个结果意味着,为了使EFH(s,t)不连通且不含孤立点,至少有2s+2个点(边)要同时发生故障。The super connectivity(super edge connectivity)is an important parameter in measuring the reliability and fault tolerance of large interconnection networks.The super conectivity(super edge conectivity)of a connected G is the minimum number of vertices(edges)that need to be delected from G in order to disconnect G without creating isolated vertices.A new interconnection network,named exchanged folded hypercube EFH(s,t),was introduced by Li el at.The super connectivity and super edge conectivity,which are two important measure in evaluating the reliability,is utilized to analyze the reliability of exchanged folded hypercube interconnection network.Then the super connectivity and super edge conectivity of exchanged folded hypercube interconnection network are obtained.We show that the super connectivity and the super edge-connectivity of EFH(s,t)are both equal to 2s+2 for 1 s t,which implies that at least 2s+2 vertices(edges)are removed to get a disconnected graph without isolated vertices.

关 键 词：超立方体 交换超立方体 交换折叠超立方体 超连通度 互连网络 

分 类 号：O157.6[理学—数学]