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

DOI10.1016/j.jctb.2004.03.008zbMath1052.05038arXivmath/0301199OpenAlexW3104211280WikidataQ56893253 ScholiaQ56893253MaRDI QIDQ598476

Alan D. Sokal, Gordon F. Royle

Publication date: 6 August 2004

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

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

zbMATH Keywords

Potts modelTutte polynomialreliability polynomialall-terminal reliabilityBrown-Colbourn conjecture

Mathematics Subject Classification ID

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

Related Items (21)

Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs ⋮ On the roots of all-terminal reliability polynomials ⋮ Maximum modulus of independence roots of graphs and trees ⋮ Tutte polynomials of bracelets ⋮ The node cop‐win reliability of unicyclic and bicyclic graphs ⋮ Network reliability: Heading out on the highway ⋮ Roots of two‐terminal reliability polynomials ⋮ Rational roots of all‐terminal reliability ⋮ On the Real Roots of Domination Polynomials ⋮ Reliability polynomials of consecutive‐k‐out‐of‐n:Fsystems have unbounded roots ⋮ Homogeneous multivariate polynomials with the half-plane property ⋮ Negative Correlation in Graphs and Matroids ⋮ Complete monotonicity for inverse powers of some combinatorially defined polynomials ⋮ Acyclic polynomials of graphs ⋮ A little statistical mechanics for the graph theorist ⋮ On the roots of domination polynomials ⋮ Polynomials with the half-plane property and the support theorems ⋮ On the roots of strongly connected reliability polynomials ⋮ On the reliability roots of simplicial complexes and matroids ⋮ Zero-free regions for multivariate tutte polynomials (alias Potts-model partition functions) of graphs and matroids ⋮ The closure of the set of roots of strongly connected reliability polynomials is the entire complex plane

Uses Software

• MPSolve
• na20

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reliability polynomials and their asymptotic limits for families of graphs
• Design, analysis, and implementation of a multiprecision polynomial rootfinder
• Topology of series-parallel networks
• Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions
• An Algebraic Proof of Kirchhoff's Network Theorem
• Roots of the Reliability Polynomials
• Graph Classes: A Survey
• Zeros of Reliability Polynomials and f-vectors of Matroids
• Chromatic Roots are Dense in the Whole Complex Plane

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