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