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 PC v (G;p) , is the expected number of connected pairs of vertices in G . An (n,m) graph G is uniformly optimally reliable if PC v (G;p) ≧ PC v (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 < ∼2 n 2 /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. © 1993 by John Wiley & Sons, Inc.