On the roots of all-terminal reliability polynomials

• Published in: Discrete mathematics 2017-06, Vol.340 (6), p.1287-1299
• Main Authors: Brown, Jason, Mol, Lucas
• Format: Article
• Language: English
• Subjects: All-terminal reliability; Brown–Colbourn conjecture; Graph polynomials; Polynomial roots
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2017.01.024

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.