2025/04/28 by Pablo Romero, Romero, Pablo
Engineering · Mathematics · #Reliability and Maintenance Optimization #Power System Reliability and Maintenance #Statistical Distribution Estimation and Applications
paper · pdf · doi:10.48550/arxiv.2504.19858
A two-terminal graph is a simple graph equipped with two distinguished vertices, called terminals. Let Tn,m be the class consisting of all nonisomorphic two-terminal graphs on n vertices and m edges. Let G be any two-terminal graph in Tn,m, and let d be any positive integer. For each ρ∈ [0,1], the d-constrained two-terminal reliability of G at ρ, denoted RGd(ρ), is the probability that G has some path of length at most d joining its terminals after each of its edges is independently deleted with probability ρ. We say G is a d-uniformly most reliable two-terminal graph (d-UMRTTG) if for each H in Tn,m and every ρ∈ [0,1] it holds that RGd(ρ)≥ RHd(ρ). Previous works studied the existence of d-UMRTTG in Tn,m when d is greater than or equal to n-1, or equivalently, when the distance constraint is dropped. In this work, a characterization of all 1-UMRTTGs and 2-UMRTTGs is given. Then, it is proved that there exists a unique 3-UMRTTG in Tn,m when n≥ 6 and 5 ≤ m ≤ 2n-3. Finally, for each d≥ 4 and each n≥ 11 it is proved that there is no d-UMRTTG in Tn,m when 20 ≤ m ≤ 3n-9 or when 3n-5 ≤ m ≤ \binomn2-2.