Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
13430942 | Discrete Applied Mathematics | 2019 | 18 Pages |
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
Kassie Archer, Christina Graves, David Milan,