k-Restricted edge connectivity for some interconnection networks

摘要

k-Restricted edge connectivity is an important parameter in measuring the reliability and fault tolerance of large interconnection networks. In this paper we present two families of graphs similar with the networks proposed by Chen et al. [Y.C. Chen, J.J.M. Tan, L.H. Hsu, S.S. Kao, Super-connectivity and super edge-connectivity for some interconnection networks, Applied Mathematics and Computation 140 (2003) 245–254] and study the k(k=2,3)-restricted edge connectivity of these graphs. In particular, as the applications of our results, the k(k=2,3)-restricted edge connectivity of the recursive circulant graphs and the n-ary k-cubes is given.