Roots of Two-Terminal Reliability

Abstract

Assume that the vertices of a graph $G$ are always operational, but the edges of $G$ are operational independently with probability $p\in [0,1]$. For fixed vertices $s$ and $t$, the \emph{two-terminal reliability} of $G$ is the probability that the operational subgraph contains an $(s,t)$-path, while the \emph{all-terminal reliability} of $G$ is the probability that the operational subgraph contains a spanning tree. Both reliabilities are polynomials in $p$, and have very similar behaviour in many respects. However, unlike all-terminal reliability, little is known about the roots of two-reliability polynomials. In a variety of ways, we shall show that the nature and location of the roots of two-terminal reliability polynomials have significantly different properties than those held by roots of the all-terminal reliability.

21 pages, 8 figures

References in corpus (2)

• Exact solutions for the two- and all-terminal reliabilities of a simple ladder network
• Exact solutions for the two- and all-terminal reliabilities of the Brecht-Colbourn ladder and the generalized fan