Boesch's conjecture on uniformly most reliable graphs

About 2 years old · traced to

Let Cn,m\mathcal{C}_{n,m} be the set of all connected simple graphs on nn vertices and mm edges. For G∈Cn,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 H∈Cn,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.

References

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.