Nonexistence of uniformly most reliable two-terminal graphs

A two-terminal graph G = (V, E) is a simple and undirected graph with two specified target vertices sand tin V. In G, if each edge survives independently with a fixed probability p, the two-terminal reliability is the probability that two target vertices are connected. A two-terminal graph is uniformly most reliable if its reliability is not less than the reliability of any other graph with same number of vertices and edges for all p. Betrand et al. proved that there is no uniformly most reliable two-terminal graph if either n >= 11 and 20 <= m <= 3n - 9 or n >= 8 and ((n)(2)) - [(n - 2)/2] <= m = ((n)(2)) - 2. In this paper, we further prove that there is no uniformly most reliable two-terminal graph if n >= 6 and 3n - 6 < m <= ((n)(2)) - 2 in a different way. (c) 2021 Elsevier B.V. All rights reserved.

Automated summary

The paper discusses the reliability of two-terminal graphs and proves that there is no uniformly most reliable two-terminal graph under certain conditions.