Reliability analysis of circulant graphs

Abstract

The circulant graphs are of particular interest as models of communication networks. In this work, we present new reliability analysis results for circulants based on the concept of restricted edge connectivity, which generalizes the super-λ property of a graph. We evaluate the restricted edge connectivity λ′ and the number of i-cutsets Ni(G), λ ≤ i < λ′, for any circulant graph explicitly. This improves the previous results on the subject. © 1998 John Wiley & Sons, Inc. Networks 31:61–65, 1998