Network reliability and the factoring theorem

Abstract In network reliability analysis, an important problem is to determine the probability that a specified subset of vertices in an undirected graph is connected. It is well known that, by using Moskowitz's factoring theorem, the reliability of a graph can be expressed in terms of the reliabilities of a graph with one fewer vertex and another with one fewer edge. The theorem can be applied recursively on the reduced graphs. The computations involved in this recursion can be represented by a binary structure such that its leaves correspond to reduced graphs whose reliabilities can be readily evaluated. In general, as the recursion progresses, series and parallel edges are created which can be reduced by using series and parallel rules of reliability assuming edges fail independently of each other. The computational complexity is a function of the number of leaves in the binary structure, and for a given graph, an optimal binary structure is the one with minimal number of leaves. In this article, a combinatorial invariant of a graph, called the domination, is established. Several important properties of the domination with regard to the topology of the graph are investigated. It is shown that for a given graph, the number of leaves in the optimal binary structure is equal to the domination of the graph and recursive application of the factoring theorem yields an optimal structure if and only if at each step the reduced graphs generated have nonzero dominations. Finally, an algorithm is presented that guarantees optimal binary structure generation and therefore an efficient implementation of the factoring theorem to compute the network reliability.