Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (13): 71-74.

Previous Articles     Next Articles

The 4-restricted edge connectivity of star networks

ZHAO Yuanqing1, JIN Xianhua2   

  1. 1.School of Computer and Information Engineering, Anyang Normal University, Anyang, Henan 455002, China
    2.Computer Teaching Department, Anyang Normal University, Anyang, Henan 455002, China
  • Online:2012-05-01 Published:2012-05-09

星网的4-限制边连通度

赵元庆1,金显华2   

  1. 1.安阳师范学院 计算机与信息工程学院,河南 安阳 455002
    2.安阳师范学院 公共计算机教学部,河南 安阳 455002

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-限制边连通度, 可靠性, 星型网络