On locally most reliable three-terminal graphs of sparse graphs

Abstract

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≡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.

Keywords

• target vertices
• rst-subgraph
• three-terminal graph
• reliability polynomial
• locally most reliable graph
• uniformly most reliable graph