On the most reliable graphs with fixed redundancy
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.01256
curl -X POST /api/v1/records/arxiv/2603.01256/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.01256/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'