折叠交叉立方体的2-外边连通度（英文）

作者：蔡学鹏^*; 杨伟

来源：中国科学技术大学学报, 2020, 50(02): 94-99.

• 交叉立方体
• 折叠交叉立方体
• g-外边连通度
• 互连网络

g-外边连通度是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且g是非负整数,如果G中存在某种边子集使得G删除这种边子集后得到的图不连通并且每个分支至少有g+1个点,则所有这种边子集中基数最小的边子集的基数称为图G的g-外边连通度,记作λg(G).由定义可知λ0(G)=λ(G)并且λ1(G)是图G的超边连通度.n维折叠交叉立方体FCQn是由交叉立方体CQn增加2n-1条边后所得.证明了λ2(FCQn)=3n-1,n≥5.

• 单位
  数理学院; 新疆农业大学