Abstract: The n-dimensional star graph, which is denoted by 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, the more reliable the network. The k-restricted edge connectivity of n-dimensional star graph is investigated and the result that the 4-restricted edge connectivity of Sn is 4n－10 for n≥4 is proved.

Key words: interconnection networks, k-restricted edge connectivity, reliability, star graph networks

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

关键词: 互连网络, k-限制边连通度, 可靠性, 星型网络