LAUSR

A two‐terminal graph is an undirected graph with two specified target vertices. If each nontarget vertex of a two‐terminal graph fails independently with the same fixed probability (and edges and target vertices are perfectly reliable), the two‐terminal node reliability is the probability that the target vertices are in the same connected component in the induced subgraph of all operational nodes. A two‐terminal graph is uniformly most reliable if its node reliability polynomial is greater than or equal to that of all other two‐terminal graphs with the same fixed number of vertices, n, and edges, m. In this paper, we show that there is always a uniformly most reliable two‐terminal graph. Furthermore, with the additional restriction that the distance between the target vertices is at least three, we completely classify which values of n and m produce a uniformly most reliable graph and which do not.