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

2003/01/31 by Gordon Royle, Alan D. Sokal · 1 citation
Mathematics · Physics and Astronomy · #math.CO #cond-mat.stat-mech #math-ph #math.MP #msc:05C99 #msc:05C40 #msc:68M10 #msc:68M15 #msc:68R10 #msc:82B20 #msc:90B15 #msc:90B18 #msc:90B25 #msc:94C15

paper · pdf · doi:10.1016/j.jctb.2004.03.008

published as J. Combin. Theory B 91, 345-360 (2004) · LaTeX2e, 17 pages. Version 2 makes a few small improvements in the exposition. To appear in Journal of Combinatorial Theory B

arxiv created 2004/06/02 · arxiv updated 2009/11/30

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₄. The univariate Brown-Colbourn conjecture is false for certain simple planar graphs obtained from K₄ 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.

Cited by

• The Degree Polynomial

Related

• Zeros of reliability polynomials and f-vectors of matroids
• Reliability Polynomials of Simple Graphs having Arbitrarily many Inflection Points
• On a conjecture on sparse binomial-type polynomials by Brown, Dilcher and Manna
• The maximum degree of planar graphs I. Series-parallel graphs
• General Parity Result and Cycle-plus-Triangles Graphs