Conditional edge connectivity properties, reliability comparisons and transitivity of graphs Original Research Article

The ith conditional edge-connectivity λi for a (simple) graph G is the minimum cardinality of a set of edges, if any, whose deletion disconnecting G and every remaining component has more than i vertices. The usual edge connectivity λ and the restricted edge connectivity λ′ of G correspond to λ0 and λ1, respectively. We first give an improved reliability comparison criterion between two regular graphs by means of λ0, λ1 and λ2. Next we prove that a vertex-transitive graph with degree d⩾4 and girth g⩾5 or an edge-transitive d-regular graph with degree d⩾4 and girth g⩾4 must have the maximum λi, namely, λi=(i+1)d−2i for 0⩽i⩽min(g−2,n/2−1), where n is the order of the graph. Finally, as an application of the above results, we show that both Ka,a (a⩾4) and Ka+1,a+1−(a+1)K2 (a⩾5) are the most reliable graphs for sufficiently small edge failure probabilities.