The Brown-Colbourn conjecture on zeros of reliability polynomials is false

Abstract

We give counterexamples to the Brown-Colbourn conjecture on reliability polynomials, in both its univariate and multivariate forms. The multivariate Brown-Colbourn conjecture is false already for the complete graph K_4. The univariate Brown-Colbourn conjecture is false for certain simple planar graphs obtained from K_4 by parallel and series expansion of edges. We show, in fact, that a graph has the multivariate Brown-Colbourn property if and only if it is series-parallel.

LaTeX2e, 17 pages. Version 2 makes a few small improvements in the exposition. To appear in Journal of Combinatorial Theory B

References in corpus (3)

• Chromatic roots are dense in the whole complex plane
• Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions
• Reliability Polynomials and their Asymptotic Limits for Families of Graphs

Cited by in corpus (8)

• Spanning forests and the q-state Potts model in the limit q \to 0
• A Little Statistical Mechanics for the Graph Theorist
• On the roots of all-terminal reliability polynomials
• Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids
• What is the probability of connecting two points ?
• Linear bound in terms of maxmaxflow for the chromatic roots of series-parallel graphs
• On the roots of the node reliability polynomial
• The blowup-polynomial of a metric space: connections to stable polynomials, graphs and their distance spectra