On the roots of all-terminal reliability polynomials

DOI10.1016/J.DISC.2017.01.024MaRDI QIDQ2400560zbMATH OpenOpenAlexFDO

Authors Jason I. Brown, L. A. S. Mól

Publication date 29 August 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

polynomial rootsgraph polynomialsall-terminal reliabilityBrown-Colbourn conjecture

Mathematics Subject Classification ID

Graph polynomials (05C31)

Abstract: Given a graph $G$ in which each edge fails independently with probability $qin[0,1],$ the all-terminal reliability of $G$ is the probability that all vertices of $G$ can communicate with one another, that is, the probability that the operational edges span the graph. The all-terminal reliability is a polynomial in $q$ whose roots (all-terminal reliability roots) were conjectured to have modulus at most $1$ by Brown and Colbourn. Royle and Sokal proved the conjecture false, finding roots of modulus larger than $1$ by a slim margin. Here, we present the first nontrivial upper bound on the modulus of any all-terminal reliability root, in terms of the number of vertices of the graph. We also find all-terminal reliability roots of larger modulus than any previously known. Finally, we consider the all-terminal reliability roots of simple graphs; we present the smallest known simple graph with all-terminal reliability roots of modulus greater than $1,$ and we find simple graphs with all-terminal reliability roots of modulus greater than $1$ that have higher edge connectivity than any previously known examples.

Recommendations

• Roots of two‐terminal reliability polynomials
• Roots of the Reliability Polynomials
• Rational roots of all‐terminal reliability
• On the roots of strongly connected reliability polynomials
• On the roots of the node reliability polynomial
• scientific article; zbMATH DE number 1295362
• Reliability polynomials of consecutive‐k‐out‐of‐n:Fsystems have unbounded roots
• scientific article; zbMATH DE number 3947973
• scientific article; zbMATH DE number 176258
• scientific article; zbMATH DE number 4053686

Cites work

• scientific article; zbMATH DE number 1741027 (Why is no real title available?)
• scientific article; zbMATH DE number 1820648 (Why is no real title available?)
• Chip firing and the Tutte polynomial
• Chromatic Roots are Dense in the Whole Complex Plane
• Homogeneous multivariate polynomials with the half-plane property
• On the Eneström-Kakeya theorem and its sharpness
• On the location of roots of independence polynomials
• On the roots of domination polynomials
• Roots of the Reliability Polynomials
• The Brown-Colbourn conjecture on zeros of reliability polynomials is false
• The closure of the set of roots of strongly connected reliability polynomials is the entire complex plane
• The evaluation of the zeros of ill-conditioned polynomials. I, II
• Zeros of Reliability Polynomials and f-vectors of Matroids
• \( h\)-vectors of matroids and logarithmic concavity

Cited in

(20)

• Roots of the Reliability Polynomials
• Invulnerability of planar two-tree networks
• Network reliability: Heading out on the highway
• Inflection points of reliability polynomials are dense in \([0,1]\)
• On the roots of the node reliability polynomial
• On the roots of strongly connected reliability polynomials
• The closure of the set of roots of strongly connected reliability polynomials is the entire complex plane
• On the real roots of domination polynomials
• On the reliability roots of simplicial complexes and matroids
• On the roots of the subtree polynomial
• Reliability polynomials and their asymptotic limits for families of graphs
• Roots of two‐terminal reliability polynomials
• Rational roots of all‐terminal reliability
• On the roots of Wiener polynomials of graphs
• Maximum modulus of independence roots of graphs and trees
• Chip firing and all-terminal network reliability bounds
• On the split reliability of graphs
• Acyclic polynomials of graphs
• The node cop‐win reliability of unicyclic and bicyclic graphs
• Reliability polynomials of consecutive‐k‐out‐of‐n:Fsystems have unbounded roots

This page was built for publication: On the roots of all-terminal reliability polynomials

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