Boesch's conjecture on uniformly most reliable graphs

Let Cn,m\mathcal{C}_{n,m} be the set of all connected simple graphs on nn vertices and mm edges. For GCn,mG\in\mathcal{C}_{n,m}, let Ni(1)(G)N_i^{(1)}(G) denote the number of spanning subgraphs of GG with ii edges and at most one connected component. A graph GG is a 0-element in Cn,m\mathcal{C}_{n,m} if

Ni(1)(G)Ni(1)(H)N_i^{(1)}(G)\geq N_i^{(1)}(H)

for every i{0,1,,m}i\in\{0,1,\ldots,m\} and every HCn,mH\in\mathcal{C}_{n,m}. A graph is uniformly most reliable if it is a 11-uniformly most reliable graph, meaning that its reliability is at least that of every graph in Cn,m\mathcal{C}_{n,m} for every edge-retention probability p[0,1]p\in[0,1].

Boesch's conjecture. Each uniformly most reliable graph in Cn,m\mathcal{C}_{n,m} is a 00-element in Cn,m\mathcal{C}_{n,m}.

Every 00-element is uniformly most reliable, since its coefficientwise inequalities imply the corresponding reliability inequalities. The converse, proposed by Boesch in 1986, remains unresolved.

Sources & referencesView supporting material

Primary source

Pablo Romero, “An algebraic characterization of strong graphs”, arXiv:2412.20702 (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.