泡形互连网络的条件连通性度量

Conditional vertex connectivity measures for bubble-sort networks

n维泡形网络是设计大规模多处理机系统时最常用的互连网络拓扑结构之一,它以n维泡形图Bn为数学模型。F是连通图G的顶点子集,使得G-F不再连通且G-F的每个连通分支都有至少有n个顶点的F的势叫做G的Rk连通度。Rk连通度是衡量网络可靠性的一个重要参数。一般来说,网络的Rk连通度越大,其可靠性越高。研究了n维泡形网络的Rk连通性;证明了在n维泡形网络中,当n≥3时,其R1连通度为2n-4;当n≥4时,其R2连通度为4n-12。

The n-dimensional bubble-sort network is one of the most popular interconnection networks in large-scale multiprocessor systems and it takes n-dimensional bubble-sort graph Bn as mathematical model.The Rk-vertex-connectivity of a connected graph G is the minimum cardinality of a set of vertices whose deletion disconnects G and any vertex of the remaining components has at least k neighbors.The Rk-vertex-connectivity is one of the most parameters to evaluate the reliability of a network.In general,the larger the Rk-vertex-connectivity of a network is,the more reliable the network is.The Rk-vertex-connectivity of n-dimensional bubble-sort graphs is investigated.The theorems that the R1-vertex-connectivity of Bn is 2n-4 for n≥3 and R2-vertex-connectivity of Bn is 4n-12 for n≥4 are proved.