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

DOI10.1016/J.JCTB.2004.03.008zbMATH Open1052.05038arXivmath/0301199OpenAlexW3104211280WikidataQ56893253 ScholiaQ56893253MaRDI QIDQ598476FDOQ598476

Authors: Alan D. Sokal, Gordon Royle 

Publication date: 6 August 2004

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/math/0301199

Recommendations

• Zeros of Reliability Polynomials and f-vectors of Matroids
• Two chromatic polynomial conjectures
• Roots of the Reliability Polynomials
• scientific article; zbMATH DE number 3947973
• Uniformly-most reliable networks do not always exist

zbMATH Keywords

Potts modelTutte polynomialreliability polynomialall-terminal reliabilityBrown-Colbourn conjecture

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Reliability, availability, maintenance, inspection in operations research (90B25) Connectivity (05C40) Reliability, testing and fault tolerance of networks and computer systems (68M15) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Stochastic network models in operations research (90B15) Communication networks in operations research (90B18) Applications of graph theory to circuits and networks (94C15) Graph theory (05C99) Network design and communication in computer systems (68M10)

Cites Work

• Design, analysis, and implementation of a multiprecision polynomial rootfinder
• Title not available (Why is that?)
• Graph Classes: A Survey
• Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Chromatic Roots are Dense in the Whole Complex Plane
• Title not available (Why is that?)
• Topology of series-parallel networks
• Roots of the Reliability Polynomials
• An Algebraic Proof of Kirchhoff's Network Theorem
• Title not available (Why is that?)
• Zeros of Reliability Polynomials and f-vectors of Matroids
• Reliability polynomials and their asymptotic limits for families of graphs

Cited In (25)

• On the reliability roots of simplicial complexes and matroids
• On the roots of strongly connected reliability polynomials
• Maximum modulus of independence roots of graphs and trees
• Zero-free regions for multivariate tutte polynomials (alias Potts-model partition functions) of graphs and matroids
• A little statistical mechanics for the graph theorist
• Homogeneous multivariate polynomials with the half-plane property
• Roots of two‐terminal reliability polynomials
• Rational roots of all‐terminal reliability
• Reliability polynomials of consecutive‐k‐out‐of‐n:Fsystems have unbounded roots
• Tutte polynomials of bracelets
• On the roots of domination polynomials
• On the real roots of domination polynomials
• Negative Correlation in Graphs and Matroids
• Roots of the Reliability Polynomials
• Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs
• The blowup-polynomial of a metric space: connections to stable polynomials, graphs and their distance spectra
• Acyclic polynomials of graphs
• Complete monotonicity for inverse powers of some combinatorially defined polynomials
• On the roots of all-terminal reliability polynomials
• The closure of the set of roots of strongly connected reliability polynomials is the entire complex plane
• The node cop‐win reliability of unicyclic and bicyclic graphs
• A Note on a Conjecture of S. Stahl
• A complete solution to a conjecture on the \({\beta}\)-polynomials of graphs
• Network reliability: Heading out on the highway
• Polynomials with the half-plane property and the support theorems

Uses Software

• MPSolve
• na20

This page was built for publication: The Brown-Colbourn conjecture on zeros of reliability polynomials is false

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q598476)