The all-terminal reliability (ATR) of an undirected graph G, denoted as R(G, q), is the probability that, when the edges are assigned independent but equal failure probabilities q, 0 < q < 1 (nodes are perfect), the surviving edges induce a spanning connected subgraph of G. A graph G with n nodes and e edges is said to be uniformly least reliable if and only if R(G, q) ≤ R(G′, q) among all connected 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 least reliable graphs for e ≥ (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 problem.
