摘要
g-外边连通度是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且g是非负整数,如果G中存在某种边子集使得G删除这种边子集后得到的图不连通并且每个分支至少有g+1个点,则所有这种边子集中基数最小的边子集的基数称为图G的g-外边连通度,记作λ_(g)(G).由定义可知λ_(0)(G)=λ(G)并且λ_(1)(G)是图G的超边连通度.n维折叠交叉立方体FCQ_(n)是由交叉立方体CQ_(n)增加2^(n-1)条边后所得.证明了λ_(2)(FCQ_(n))=3n-1,n≥5.
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.Note thatλ_(0)(G)=λ(G)andλ_(1)(G)is the super edge connectivity of G.The n-dimensional folded crossed cube FCQ_(n)is obtained from the crossed cube CQ_(n)by adding extra 2^(n-1)edges.Here it was proved thatλ_(2)(FCQ_(n))=3n-1 for n≥5.
作者
蔡学鹏
杨伟
CAI Xuepeng;YANG Wei(College of Mathematics and Physics, Xinjiang Agricultural University, Urumqi 830052, China)
基金
Supported by College Scientific Research Project of Xinjiang(XJEDU2018Y021)
National College Students Innovation and Entrepreneurship Training Program (201810758035)
