Some conjectured uniformly optimal reliable networks

We consider all-terminal reliability, one of the more popular models in the field of network reliability. A graph with n nodes and e edges, where the nodes are perfectly reliable and the edges survive independently with equal probability p, is said to be a uniformly optimally reliable graph if it has for all values of p (0 less than or equal to p less than or equal to 1) an equal or higher reliability among all graphs with the same number of nodes and edges. Boesch et al. verified the existence of uniformly optimally reliable graphs for e = n – 1, e = n, e = n + 1, and e = n + 2; he has also given a conjecture for e = n + 3; Wang proved this conjecture. In this article, we present four new infinite families of graphs that we conjecture to be uniformly optimal.