Counterexample to a Boesch's conjecture.

Abstract

A key issue in network reliability analysis. A graph with n nodes and whose e edges fail independently with probability p is an Uniformly Most Reliable Graph (UMRG) if it has the highest reliability among all graphs with the same order and size for every value of p. The all-terminal reliability is a polynomial in p which defines the probability of a network to remain connected if some of its components fail. If the coefficients of the reliability polynomial are maximized by a graph, that graph is called Strong Uniformly Most Reliable Graph (SUMRG) and it should be UMRG. An exhaustive computer search of the SUMRG with vertices up to 9 is done. Regular graphs with 10 to 14 vertices that maximize tree number are proposed as candidates to UMRG. As an outstanding result a UMRG with 9 vertices and 18 edges which has girth 3 is found, so smaller than the conjectured by Boesch in 1986.