2022/12/07 by Nicole Rosenstock, Rosenstock, Nicole, Eduardo Canale +1
Engineering · Decision Sciences · Computer Science · #Reliability and Maintenance Optimization #Risk and Safety Analysis #Software Reliability and Analysis Research
paper · pdf · doi:10.48550/arxiv.2212.03912
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. A new conjecture about UMRG's topology is posed here: the (n,e)-UMRG is (k-1)C3∪ C3+r whenever n=3k+r,n≥5 and e=n(n-3)/2. A reformulation of Boesch's conjecture is presented stating that if a (n, kn/2)-UMRG exists and it has girth g, then it has maximum girth among all k-regular (n,kn/2) graphs and minimum number of g-cycles among those k-regular (n,kn/2) graphs with girth g.