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

On 2-extra edge connectivity of folded crossed cube

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

Abstract: The g-extra edge connectivity is an important parameter in measuring the reliability and fault tolerance of large interconnection networks. Let G be a connected graph and an integer g≥0, the g-extra edge connectivity of G, denoted by λg(G), is the minimum cardinality of a set of edges of G, if it exists, whose deletion disconnects G and leaves each remaining component to have at least g+1 vertices.