Ath–Sobel conjecture on sparse uniformly most reliable graphs

Let Cn,m\mathcal C_{n,m} be the class of connected simple graphs on nn vertices and mm edges, and define its corank by c=mn+1c=m-n+1. A uniformly most reliable graph (UMRG) is a graph in this class whose reliability is at least that of every other member for every edge-failure probability ρ[0,1]\rho\in[0,1]. Ath–Sobel conjecture. If Cn,m\mathcal C_{n,m} is nonempty, c{5,6,7,8}c\in\{5,6,7,8\}, and n2c2n\geq 2c-2, then Cn,m\mathcal C_{n,m} contains at least one UMRG. The conjecture extends the known characterization for corank at most 44; the supplied text gives no resolution of the stated cases.

Sources & referencesView supporting material

Primary source

Pablo Romero, “There are finitely many uniformly most reliable graphs of corank 5”, arXiv:2412.20684 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.