Article ID Journal Published Year Pages File Type
13430942 Discrete Applied Mathematics 2019 18 Pages PDF
Abstract
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∈[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 n2−n+12 or n2−n+32, there exists a unique uniformly most reliable graph, and we give its construction.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,