ON THE NONEXISTENCE OF UNIFORMLY OPTIMAL GRAPHS FOR PAIR-CONNECTED RELIABILITY

We consider probabilistic graphs G = (V, E) in which each edge xy member-of E fails independently with probability q. The reliability measure studied is pair-connectivity, the expected number of pairs of connected vertices. We examine how the coefficients of the pair-connected reliability polynomial are determined by the subgraph structure of G, and we use these results to show that in most cases there does not exist a uniformly optimal n-vertex, m-edge graph.