2019/12/23 by Sun Xie, Xie, Sun, Haixing Zhao +3
Engineering · #Advanced Battery Technologies Research #Combinatorics (math.CO) #FOS: Mathematics #Reliability and Maintenance Optimization
paper · pdf · doi:10.48550/arxiv.1912.11361
openalex publication_date 2019/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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≥7 and \binomn2-\lfloor(n-3)/(2)\rfloor≤ m≤\binomn2-2. Finally, some uniformly most reliable graphs are given for n vertices and m edges, where 4≤ n≤ 6 and m=\binomn2-2 or n≥5 and m=\binomn2-1.