UNIFORMLY LEAST RELIABLE GRAPHS

The all-terminal reliability (ATR) of an undirected graph G, denoted a s R(G, q), is the probability that, when the edges are assigned indepe ndent but equal failure probabilities q, 0 < q < 1 (nodes are perfect) , the surviving edges induce a spanning connected subgraph of G. A gra ph G with n nodes and e edges is said to be uniformly least reliable i f and only ii R(G, q) less than or equal to R(G', q) among all connect ed G' with the same number of nodes and edges as G and for all failure probabilities 0 < q < 1. In this paper, we characterize uniformly lea st reliable graphs for e greater than or equal to (n - 1)(n - 2)/2 + 1 . We note that, unlike general graphs, for which computing the ATR has been shown to be NP-hard, the ATR of these graphs can be computed in polynomial time, providing an efficient lower bound for the general pr oblem. (C) 1996 John Wiley & Sons, Inc.