计算机工程与应用2011，Vol.47Issue(22)：13-16,4.DOI:10.3778/j.issn.1002-8331.2011.22.004
泡形互连网络的条件连通性度量
Conditional vertex connectivity measures for bubble-sort networks
摘要
Abstract
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 R' -vertex-connectivity of Bn is 2n-4 for n≥3 and R2-vertex-connectivity of Bn is 4n-12 for n≥4 are proved.关键词
互连网络/条件点连通度/泡形网络/可靠性Key words
interconnection networks/conditional vertex connectivity/bubble-sort graphs/reliability分类
计算机与自动化引用本文复制引用
杨玉星,王世英..泡形互连网络的条件连通性度量[J].计算机工程与应用,2011,47(22):13-16,4.基金项目
国家自然科学基金(the National Natural Science Foundation of China under Grant No.61070229) （the National Natural Science Foundation of China under Grant No.61070229）
山西省自然科学基金(No.2011021004). （No.2011021004）
