Uniformly Most Reliable Three-Terminal Graph of Dense Graphs

A graph with specified target vertices in vertex set is a - terminal graph. The - terminal reliability is the connection probability of the fixed target vertices in a - terminal graph when every edge of this graph survives independently with probability . For the class of two-terminal graphs with a large number of edges, Betrand, Goff, Graves, and Sun constructed a locally most reliable two-terminal graph for close to 1 and illustrated by a counterexample that this locally most reliable graph is not the uniformly most reliable two-terminal graph. At the same time, they also determined that there is a uniformly most reliable two-terminal graph in the class obtained by deleting an edge from the complete graph with two target vertices. This article focuses on the uniformly most reliable three-terminal graph of dense graphs with vertices and edges. First, we give the locally most reliable three-terminal graphs of and in certain ranges for close to 0 and 1. Then, it is proved that there is no uniformly most reliable three-terminal graph with specific and , where and . Finally, some uniformly most reliable graphs are given for vertices and edges, where and or and .