Brown–Colbourn conjecture on all-terminal reliability roots

Let G=(V,E)G=(V,E) be a connected graph, and let Rel(G;q)\mathrm{Rel}(G;q) denote its all-terminal reliability polynomial in the edge-failure probability qq. A complex number zz is an all-terminal reliability root if Rel(G;z)=0\mathrm{Rel}(G;z)=0. Brown–Colbourn conjecture. If zz is a root of Rel(G;q)\mathrm{Rel}(G;q), then

z1.|z|\leq 1.

Equivalently, all all-terminal reliability roots lie in the unit disk. The conjecture is false in general, although it holds for series-parallel graphs; counterexamples were found by Sokal and Royle.

Sources & referencesView supporting material

Primary source

Jason Brown and Lucas Mol, “On the roots of all-terminal reliability polynomials”, arXiv:1703.10566 (2017).

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.