Boesch's conjecture on uniformly most reliable graphs
Let be the set of all connected simple graphs on vertices and edges. For , let denote the number of spanning subgraphs of with edges and at most one connected component. A graph is a 0-element in if
for every and every . A graph is uniformly most reliable if it is a -uniformly most reliable graph, meaning that its reliability is at least that of every graph in for every edge-retention probability .
Boesch's conjecture. Each uniformly most reliable graph in is a -element in .
Every -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
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.