3-restricted edge connectivity of star graph networks
Jin Xianhua · Computer Engineering and Applications Journal · 2012
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.