The most reliable series‐parallel networks

The design of reliable communications networks is an interesting and important topic. Perhaps the most common measure of reliability is a probabilistic one: the probability that a network is connected given the possibility of statistically independent line failures. In general, this is not efficiently computable. In this article, we develop a formula for the reliability of the most reliable maximal series‐parallel networks. The most reliable maximal series‐parallel networks are those maximal series‐parallel networks with the minimum number of vertices of degree 2, independent of many of the simpler reliability estimates. A two‐dimensional recurrence relating networks of varying sizes and edge deficiencies provides a generating function which in turn is exploited to give a simple closed expression for reliability.