On uniformly optimally reliable graphs for pair‐connected reliability with vertex failures

Let G be a probabilistic (n,m) graph in which each vertex exists independently with fixed probability p, 0 < p < 1. Pair‐connected reliability of G, denoted PCv(G;p), is the expected number of connected pairs of vertices in G. An (n,m) graph G is uniformly optimally reliable if PCv(G;p) ≧ PCv(H;p) for all p, 0 < p < 1, over all (n,m) graphs H. It is shown that there does not exist a uniformly optimally reliable (n,m) graph whenever n ≦ m < ∼2n2/9. However, such graphs do exist for some other values of m. In particular, it is established that every complete k‐partite pseudoregular graph on n vertices, 2 ≦ k < n, is uniformly optimally reliable.