Ath–Sobel conjecture on sparse uniformly most reliable graphs

About 2 years old · traced to

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=m−n+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 n≥2c−2n\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.

References

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.