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

摘要

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.%星型互连网络是并行与分布式处理领域中最流行的互连网络之一,它以n维星图作为拓扑结构.k-限制边连通度是衡量网络的可靠性的参数之一.一般来说,一个网络的k-限制边连通度越大,其连通性就越好.研究了星型互连网络的k限制边连通度;证明了当n≥3时,n维星型互连网络的3-限制连通度为3n -7.