Conditional vertex connectivity measures for bubble-sort networks
Shiying Wang · Computer Engineering and Applications Journal · 2011
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.