On the roots of the node reliability polynomial

DOI10.1002/NET.21697zbMATH Open1387.05116arXiv1607.08496OpenAlexW2503583255MaRDI QIDQ4639686FDOQ4639686

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

Publication date: 11 May 2018

Published in: Networks (Search for Journal in Brave)

Abstract: Given a graph $G$ whose edges are perfectly reliable and whose nodes each operate independently with probability $pin[0,1],$ the node reliability of $G$ is the probability that at least one node is operational and that the operational nodes can all communicate in the subgraph that they induce; it is the analogous node measure of robustness to the well studied extit{all-terminal reliability}, where the nodes are perfectly reliable but the edges fail randomly. In sharp contrast to what is known about the roots of the all-terminal reliability polynomial, we show that the node reliability polynomial of any connected graph on at least three nodes has a nonreal polynomial root, the collection of real roots of all node reliability polynomials is unbounded, and the collection of complex roots of all node reliability polynomials is dense in the entire complex plane.

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

Recommendations

• On the roots of all-terminal reliability polynomials
• The shape of node reliability
• Roots of the Reliability Polynomials
• Inflection points of reliability polynomials are dense in \([0,1]\)
• On the roots of strongly connected reliability polynomials

zbMATH Keywords

graph polynomialpolynomial rootall-terminal reliabilitynode reliabilityclosure of rootslimit of roots

Mathematics Subject Classification ID

Graph polynomials (05C31) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cited In (15)

• On the reliability roots of simplicial complexes and matroids
• Maximal intervals of decrease and inflection points for node reliability
• Sixty years of network reliability
• On the roots of strongly connected reliability polynomials
• The shape of node reliability
• Roots of two‐terminal reliability polynomials
• Reliability polynomials of consecutive‐k‐out‐of‐n:Fsystems have unbounded roots
• On the mean connected induced subgraph order of cographs
• Roots of the Reliability 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
• 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 the node reliability polynomial

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