折叠交叉立方体的2-限制性边通度  

On the 2-restricted Edge Connectivity of Folded Crossed Cubes

作　　者：蔡学鹏 樊丹丹 徐刚刚 CAI Xuepeng;FAN Dandan;XU Ganggang(College of Mathematics and Physics,Xinjiang Agricultural University,Urumqi 830052)

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

出　　处：《工程数学学报》2022年第3期477-486,共10页Chinese Journal of Engineering Mathematics

基　　金：新疆自然科学基金(2021D01A98);新疆青年科学基金(2019D01B17);新疆农业大学大学生创新创业训练计划项目(S202110758043)。

摘　　要：h-限制性边连通度是衡量大型互连网络可靠性和容错性的一个重要参数。设G是连通图且h是非负整数,如果G中存在某种边子集,使得G删除这种边子集后得到的图不连通并且每个分支中点的度至少是h,则所有这种边子集中基数最小的边子集的基数称为图G的h-限制性边连通度。n-维折叠交叉立方体是由n-维交叉立方体增加一些补边后所得。对于此类问题,首先利用2-限制性边连通度作为可靠性的重要度量,对折叠交叉立方体网络的可靠性进行分析,然后得到折叠交叉立方体的2-限制性边连通度,最后证明并确定n-维折叠交叉立方体的2-限制性边连通度等于4n-4(n≥4)。这个结果意味着,为了使n-维折叠交叉立方体不连通且每个分支中没有度数小于2的点,至少应有4n-4条边同时发生故障。The h-restricted edge connectivity is an important parameter in measuring the reliability and fault tolerance of large interconnection networks.Let G be a connected graph and h be a non-negative integer.The h-restricted edge connectivity of G is the minimum cardinality of a set of edges,if it exists,whose deletion disconnects G and the degree of each vertex in every remaining component is at least h.The n-dimensional folded crossed cube is obtained from the n-dimensional crossed cube by adding extra edges.The h-restricted edge connectivity,which is an important measure in evaluating the reliability,is utilized to analyze the reliability of folded crossed cube.Then the h-restricted edge connectivity of folded crossed cubes is obtained.Finally,it is proved that the 2-restricted edge connectivity of a folded crossed cube is equal to 4n-4(n≥4).It means that at least 4n-4 edges must be removed to disconnect a n-dimensional folded crossed cube,provided that the removal of these vertices does not leave a vertex that has degree less than two.

关 键 词：折叠交叉立方体 限制性边连通度 互连网络 

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