The shape of node reliability

DOI10.1016/J.DAM.2017.11.035MaRDI QIDQ1701111zbMATH OpenOpenAlexFDO

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

Publication date 22 February 2018

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

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

zbMATH Keywords

coherencegraph theoryall-terminal reliabilitynode reliability\(S\)-shaped

Mathematics Subject Classification ID

Graph polynomials (05C31)

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. We study analytic properties of the node reliability on the interval $[0,1]$ including monotonicity, concavity, and fixed points. Our results show a stark contrast between this model of network robustness and models that arise from coherent set systems (including all-terminal, two-terminal and K-terminal reliability).

Recommendations

• scientific article; zbMATH DE number 1185593
• scientific article; zbMATH DE number 1444280
• On the roots of the node reliability polynomial
• On reliability of graphs with node failures
• Reliability-Equivalent-Separation of a Node
• Reliability properties of the hypercube network
• Bounding the Reliability of Networks
• Maximal intervals of decrease and inflection points for node reliability

Cites work

• scientific article; zbMATH DE number 5944468 (Why is no real title available?)
• scientific article; zbMATH DE number 1444280 (Why is no real title available?)
• Binary trees with the largest number of subtrees
• Computing residual connectedness reliability for restricted networks
• Enumeration of subtrees of trees
• Multi-Component Systems and Structures and Their Reliability
• On reliability of graphs with node failures
• On subtrees of trees
• Reliability polynomials having arbitrarily many inflection points
• The Complexity of the Residual Node Connectedness Reliability Problem
• The minimal number of subtrees of a tree
• The minimal number of subtrees with a given degree sequence
• The number of subtrees of trees with given degree sequence
• The traveling salesman problem in bounded degree graphs
• Uniformly optimal graphs in some classes of graphs with node failures

Cited in

(6)

• Maximal intervals of decrease and inflection points for node reliability
• On the mean connected induced subgraph order of cographs
• On the roots of the node reliability polynomial
• The node cop‐win reliability of unicyclic and bicyclic graphs
• Node partition formula for directed graph reliability
• Network reliability: Heading out on the highway

This page was built for publication: The shape of node reliability

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