Building uniformly most-reliable networks by iterative augmentation

A fundamental problem in network reliability analysis is to find the connectedness probability of a random graph, subject to perfect nodes and link failures. If, in addition, we consider independent link failures with identical probability ρ, the connectedness probability is known as the all-terminal reliability. It is well-known that the all-terminal reliability is a polynomial in the variable ρ ϵ [0,1], and its determination belongs to the class of NP-Hard problems. In this paper we address the following network design problem: given a fixed number of nodes and links p and q, find the graph that maximizes the reliability polynomial uniformly on the compact set ρ ϵ [0,1] for all (p, q)-graphs whenever it exists. These graphs are called uniformly most-reliable graphs. There exists easy graphs, where the reliability polynomial is obtained in a straightforward manner. The interplay between easy graphs and uniformly most-reliable graphs is first studied. Then, Wagner graph is discovered as a uniformly most-reliable graph, inspired by greedy augmentations of a cycle. The paper is closed with a conjecture on the existence of (n, n + 4) uniformly most-reliable graphs.