星型网络的3-限制边连通性

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (7): 81-83.

星型网络的3-限制边连通性

赵元庆1，金显华2

1.安阳师范学院计算机与信息工程学院，河南安阳 455002
2.安阳师范学院计算中心，河南安阳 455002

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2012-03-01 发布日期:2012-03-01

3-restricted edge connectivity of star graph networks

ZHAO Yuanqing1, JIN Xianhua2

1.School of Computer and Information Engineering, Anyang Normal University, Anyang, Henan 455002, China
2.Computing Center, Anyang Normal University, Anyang, Henan 455002, China

Received:1900-01-01 Revised:1900-01-01 Online:2012-03-01 Published:2012-03-01

摘要/Abstract

摘要： 星型互连网络是并行与分布式处理领域中最流行的互连网络之一，它以n维星图作为拓扑结构。k-限制边连通度是衡量网络的可靠性的参数之一。一般来说，一个网络的k-限制边连通度越大，其连通性就越好。研究了星型互连网络的k限制边连通度；证明了当n≥3时，n维星型互连网络的3-限制连通度为3n－7。

Abstract: The n-dimensional star graph Sn is one of the most popular interconnection networks and the k-restricted edge connectivity of a graph G is the minimum cardinality of a set of edges, if any, whose deletion disconnects G and every remaining component has at least k vertices. The k-restricted edge connectivity is one of the most parameters to evaluate the reliability of a network. In general, the larger the k-restricted edge connectivity of a network is, the more reliable the network is. The k-restricted edge connectivity of n-dimensional star graph is investigated and the result that the 3-restricted edge connectivity of Sn is 3n－7 for n≥3 is proved.

赵元庆1，金显华2. 星型网络的3-限制边连通性[J]. 计算机工程与应用, 2012, 48(7): 81-83.

ZHAO Yuanqing1, JIN Xianhua2. 3-restricted edge connectivity of star graph networks[J]. Computer Engineering and Applications, 2012, 48(7): 81-83.