Uniformly most reliable three-terminal graph of dense graphs

Abstract

A graph $G$ with $k$ specified target vertices in vertex set is a $k$-terminal graph. The $k$-terminal reliability is the connection probability of the fixed $k$ target vertices in a $k$-terminal graph when every edge of this graph survives independently with probability $p$. 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 $p$ 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 $n$ vertices and $m$ edges. First, we give the locally most reliable three-terminal graphs of $n$ and $m$ in certain ranges for $p$ close to $0$ and $1$. Then, it is proved that there is no uniformly most reliable three-terminal graph with specific $n$ and $m$, where $n\ge 7$ and $\left(\genfrac{}{}{0ex}{}{n}{2}\right)-\lfloor \frac{n-3}{2}\rfloor \le m\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)-2$. Finally, some uniformly most reliable graphs are given for $n$ vertices and $m$ edges, where $4\le n\le 6$ and $m=\left(\genfrac{}{}{0ex}{}{n}{2}\right)-2$ or $n\ge 5$ and $m=\left(\genfrac{}{}{0ex}{}{n}{2}\right)-1$.