Classes of uniformly most reliable graphs for all-terminal reliability

摘要

The all-terminal reliability polynomial of a graph G is the probability that G remains connected if each edge is independently included with fixed probability p. Among all graphs with a fixed number of n vertices and m edges, a graph is uniformly most reliable if its reliability polynomial is greater than or equal to all other graphs on the same number of vertices and edges for every value of p is an element of [0, 1]. We find a new class of graphs that are uniformly most reliable. Specifically, we show that when n >= 5 is odd and m is either ((n)(2)) - n+1/2 or ((n)(2)) - n+3/2 , there exists a unique uniformly most reliable graph, and we give its construction. (C) 2019 Elsevier B.V. All rights reserved.