完全对换网络的限制连通度  

The restricted connectivity of complete-transposition networks

作　　者：王国亮[1] 师海忠[1] 

机构地区：[1]西北师范大学数学与统计学院,兰州730070

出　　处：《运筹学学报》2013年第3期57-64,共8页Operations Research Transactions

基　　金：甘肃省自然科学基金(No.ZS991-A25-017-G)

摘　　要：完全对换网络是基于Cayley图模型的一类重要互连网络.一个图G的k-限制点(边)连通度是使得G-F不连通且每个分支至少有k个顶点的最小点(边)子集F的基数,记作kk(λk).它是衡量网络可靠性的重要参数之一,也是图的容错性的一种精化了的度量.一般地,网络的k-限制点(边)连通度越大,它的连通性就越好.证明了完全对换网络CTn的2-限制点(边)连通度和3-限制点(边)连通度,具体来说:当n≥4时,k2(CTn)=n(n-1)-2,k3(CTn)=3n(n-1)/2-6;当n≥3时,λ3(CTn)=n(n-1)-2,λ3(CTn)=3n(n-1)/2-4.Complete-transposition networks are a class of important Cayley graphs in networks design. The k-restricted vertex（edge）-connectivity of a graph G is the minimum cardinality of a set of vertices （edges） in G whose removal results in disconnected and each component has at least k vertices, denoted by kk （λk）. The k-restricted vertex（edge）- connectivity is one of the most parameters to evaluate the reliability of a network, it is also a refined measure of the fault tolerance of the graph. In general, the larger the k-restricted vertex（edge）-connectivity of a network, the more reliable the network. The paper proves that 2-restricted vertex（edge）-connectivity and 3-restricted vertex（edge）-connectivity of complete-transposition networks, that is, when n ≥ 4,k2（CTn）=n（n-1）-2,k3（CTn）=3n（n-1）/2-6,when n 〉/3,λ2（CTn）=n（n-1）-2,λ3（CTn）=3n（n-1）/2-4.

关 键 词：互连网络 CAYLEY图 完全对换网络 限制点连通度 限制边连通度 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]