| Popis: |
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 n 2 − n + 1 2 or n 2 − n + 3 2 , there exists a unique uniformly most reliable graph, and we give its construction. |
Full Text from ScienceDirect