折叠交叉超立方体的2-额外连通度和2-额外边连通度

摘要

有各种各样的方法去衡量不同网络的可靠性和容错性.一个连通图G的g-额外连通度κ_g（g-额外边连通度λ_g）是顶点数最小的顶点集S（边数最少的边集S）,使得G-S不连通，并且剩下的每个连通分支含有的顶点数至少是g+1.探究n-维折叠交叉超立方体FCQ_n的2-额外连通度和2-额外边连通度，证明得到如下结论：当n≥8时，κ₂（FCQ_n）=3n-2;当n≥5时，λ₂（FCQ_n）=3n-1.

关键词

折叠交叉超立方体 / 连通度 / 2-额外连通度 / 2-额外边连通度 / 可靠性