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 K4. The univariate Brown-Colbourn conjecture is false for certain simple planar graphs obtained from K4 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.
Original language | English (US) |
---|---|
Pages (from-to) | 345-360 |
Number of pages | 16 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 91 |
Issue number | 2 |
DOIs | |
State | Published - Jul 2004 |
Keywords
- All-terminal reliability
- Brown-Colbourn conjecture
- Potts model
- Reliability polynomial
- Tutte polynomial
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics