在线咨询
中国工业与应用数学学会会刊
主管:中华人民共和国教育部
主办:西安交通大学
ISSN 1005-3085  CN 61-1269/O1

工程数学学报 ›› 2022, Vol. 39 ›› Issue (3): 477-486.doi: 10.3969/j.issn.1005-3085.2022.03.011

• • 上一篇    下一篇

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

蔡学鹏,   樊丹丹,   徐刚刚   

  1. 新疆农业大学数理学院,乌鲁木齐 830052
  • 出版日期:2022-06-15 发布日期:2022-08-15
  • 基金资助:
    新疆自然科学基金 (2021D01A98);新疆青年科学基金 (2019D01B17);新疆农业大学大学生创新创业训练计划项目 (S202110758043).

On the 2-restricted Edge Connectivity of Folded Crossed Cubes

CAI Xuepeng,   FAN Dandan,   XU Ganggang   

  1. College of Mathematics and Physics, Xinjiang Agricultural University, Urumqi 830052
  • Online:2022-06-15 Published:2022-08-15
  • Supported by:
    The Natural Science Foundation of Xinjiang (2021D01A98); the Youth Science Foundation of Xinjiang (2019D01B17); the College Students Innovation and Entrepreneurship Training Program (S202110758043).

摘要:

$h$-限制性边连通度是衡量大型互连网络可靠性和容错性的一个重要参数。设 $G$ 是连通图且 $h$ 是非负整数,如果 $G$ 中存在某种边子集,使得 $G$ 删除这种边子集后得到的图不连通并且每个分支中点的度至少是 $h$,则所有这种边子集中基数最小的边子集的基数称为图 $G$ 的 $h$-限制性边连通度。$n$-维折叠交叉立方体是由 $n$-维交叉立方体增加一些补边后所得。对于此类问题,首先利用 $2$-限制性边连通度作为可靠性的重要度量,对折叠交叉立方体网络的可靠性进行分析,然后得到折叠交叉立方体的 $2$-限制性边连通度,最后证明并确定 $n$-维折叠交叉立方体的 $2$-限制性边连通度等于 $4n-4 (n\geq 4)$。这个结果意味着,为了使 $n$-维折叠交叉立方体不连通且每个分支中没有度数小于 2 的点,至少应有 $4n-4$ 条边同时发生故障。

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

Abstract:

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\geq 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.

Key words: folded crossed cube, restricted edge connectivity, interconnection network

中图分类号: