ON UNIFORMLY OPTIMALLY RELIABLE GRAPHS FOR PAIR-CONNECTED RELIABILITYWITH VERTEX FAILURES

Let G be a probabilistic (n,m) graph in which each vertex exists indep endently with fixed probability p, 0 < p < 1. Pair-connected reliabili ty 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) greater-than-or-equal-to 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 unifo rmly optimally reliable (n,m) graph whenever n less-than-or-equal-to m < approximately 2n2/9. However, such graphs do exist for some other v alues of m. In particular, it is established that every complete k-par tite pseudoregular graph on n vertices, 2 less-than-or-equal-to k < n, is uniformly optimally reliable.