On the roots of all-terminal reliability polynomials

Given a graph G in which each edge fails independently with probability q∈[0,1], the all-terminal reliability of G is the probability that all vertices of G can communicate with one another, that is, the probability that the operational edges span the graph. The all-terminal reliability is a polynomial in q whose roots (all-terminal reliability roots) were conjectured to have modulus at most 1 by Brown and Colbourn. Royle and Sokal proved the conjecture false, finding roots of modulus larger than 1 by a slim margin. Here, we present the first nontrivial upper bound on the modulus of any all-terminal reliability root, in terms of the number of vertices of the graph. We also find all-terminal reliability roots of larger modulus than any previously known. Finally, we consider the all-terminal reliability roots of simple graphs; we present the smallest known simple graph with all-terminal reliability roots of modulus greater than 1, and we find simple graphs with all-terminal reliability roots of modulus greater than 1 that have higher edge connectivity than any previously known examples.