Id: arxiv/2603.01256 Url: https://arxiv.org/abs/2603.01256 Tags: math.CO, cs.DM Score: 0 Title: On the most reliable graphs with fixed redundancy Domain: math.CO Source: arxiv Authors: Rotem Brand, Reuven Cohen, Simi Haber, Baruch Barzel Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-01 Page: https://delphi.science/r/arxiv/2603.01256 The all-terminal reliability of a graph $G$ is the probability that $G$ remains connected when each edge fails independently with probability $p$. For fixed $n$ and $m$, the uniformly most reliable problem asks which graph with $n$ vertices and $m$ edges maximizes reliability for all $p \in [0,1]$. Although such graphs do not always exist, optimal graphs in the regime $p \to 0$ always do and are determined by the structure of their minimal cut sets. We establish a structural characterization of graphs that are most reliable near $p=0$. Our results partially resolve a conjecture of Bourel et…