Conditional edge connectivity properties, reliability comparisons and transitivity of graphs (Q1850060)

For a simple undirected finite graph \(G\) and for each nonnegative integer \(i\), let \(\lambda_{i}\) denote the size of a smallest separating set \(S\subset E(G)\) such that every component of \(G-S\) contains at least \(i+1\) vertices. Suppose that \(G\) is a connected \(d\)-valent graph (\(d\geq 4\)) on at least 6 vertices. If \(G\) is either (i) edge-transitive with girth \(g\geq 4\) or (ii) vertex-transitive with girth \(g\geq 5\), then \(\lambda_{i}=(i+1)d-2i\) for \(0\leq i\leq\min\{g-2,n/2-1\}\). Suppose that the edges of \(G\) fail independently with probability \(\rho\in(0,1)\), and let \(P(G,\rho)\) denote the polynomial (in \(\rho\)) that measures the probability of \(G\) being not connected. Call \(G\) locally most reliable (LMR) if \(P(G,\rho)\leq P(G',\rho)\) for all graphs \(G'\) having the same numbers of vertices and edges as \(G\) and all sufficiently small values of \(\rho\). It is shown that for \(a\geq 5\) the complete bipartite graph \(K_{a+1,a+1}\) minus a 1-factor is the only LMR graph on \(2(a+1)\) vertices and \(a(a+1)\) edges.