On locally most reliable three-terminal graphs of sparse graphs

A network structure with n vertices and m edges is practically represented by a graph with n vertices and m edges. The graph with k fixed target vertices is called a k-terminal graph. This article studies the locally most reliable simple sparse three-terminal graphs, in which each edge survives independently with probability p. For p close to 0 or 1, the locally most reliable three-terminal graphs with n vertices and m edges are determined, where n >= 5 and 9 <= m <= 4n - 10. Finally, we prove that there is no uniformly most reliable three-terminal graph for n >= 5, 11 < m <= 3n - 5 and m equivalent to 2(mod3) and for n >= 7, 3n 5 < m <= 4n - 10. This research provides helpful guidance for constructing a highly reliable network with three target vertices.

Automated summary

This article investigates the locally most reliable simple sparse three-terminal graphs and determines the most reliable three-terminal graphs under specific conditions. The research findings provide helpful guidance for constructing highly reliable networks.