On the roots of all-terminal reliability polynomials

DOI10.1016/J.DISC.2017.01.024zbMATH Open1369.05115arXiv1703.10566OpenAlexW2600202171MaRDI QIDQ2400560FDOQ2400560

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

Publication date: 29 August 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

polynomial rootsgraph polynomialsall-terminal reliabilityBrown-Colbourn conjecture

Mathematics Subject Classification ID

Graph polynomials (05C31)

Cites Work

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

Cited In (20)

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

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)