Conditional edge connectivity properties, reliability comparisons and transitivity of graphs

The ith conditional edge-connectivity lambda(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 lambda and the restricted edge connectivity lambda' of G correspond to lambda(0) and lambda(1), respectively. We first give an improved reliability comparison criterion between two regular graphs by means of lambda(0), lambda(1), and lambda(2). Next we prove that a vertex-transitive graph with degree d greater than or equal to 4 and girth g greater than or equal to 5 or an edge-transitive d-regular graph with degree d greater than or equal to 4 and girth g greater than or equal to 4 must have the maximum lambda(i), namely, lambda(i) = (i + 1)d - 2i for 0 less than or equal to i less than or equal to 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 K-a,K-a (a greater than or equal to 4) and K-a+1,K-a+1 - (a + 1)K-2 (a greater than or equal to 5) are the most reliable graphs for sufficiently small edge failure probabilities. (C) 2002 Elsevier Science B.V. All rights reserved.