Boesch's conjecture on uniformly most reliable graphs
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.