Name
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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.jctb.2004.03.008 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
reliability polynomial,tutte polynomial,90b15,82b20,brown–colbourn conjecture,potts model.,94c15 (secondary),all-terminal reliability,brown-colbourn conjecture,multivariate form,90b18,05c99 (primary),05c40,68m10,univariate brown-colbourn conjecture,certain simple planar graph,68m15,potts model,series parallel,complete graph k4,90b25,68r10,series expansion,multivariate brown colbourn property,multivariate brown colbourn conjecture,complete graph,planar graph,statistical mechanics | Complete graph,Discrete mathematics,Combinatorics,Tutte polynomial,Counterexample,Univariate,Graph minor,Collatz conjecture,Planar graph,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
91 | 2 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
14 | 1.23 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gordon Royle | 1 | 39 | 5.05 |
| Alan D. Sokal | 2 | 253 | 22.25 |