2023/06/06 by Jason I. Brown, Brown, Jason I., Isaac McMullin +1
Engineering · #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #Reliability and Maintenance Optimization
paper · pdf · doi:10.48550/arxiv.2306.03884
openalex publication_date 2023/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
A common model of robustness of a graph against random failures has all vertices operational, but the edges independently operational with probability p. One can ask for the probability that all vertices can communicate (\em all-terminal reliability) or that two specific vertices (or \em terminals) can communicate with each other (\em two-terminal reliability). A relatively new measure is \em split reliability, where for two fixed vertices s and t, we consider the probability that every vertex communicates with one of s or t, but not both. In this paper, we explore the existence for fixed numbers n ≥ 2 and m ≥ n-1 of an \em optimal connected (n,m)-graph Gn,m for split reliability, that is, a connected graph with n vertices and m edges for which for any other such graph H, the split reliability of Gn,m is at least as large as that of H, for \em all values of p ∈ [0,1]. Unlike the similar problems for all-terminal and two-terminal reliability, where only partial results are known, we completely solve the issue for split reliability, where we show that there is an optimal (n,m)-graph for split reliability if and only if n≤ 3, m=n-1, or n=m=4.