13 problems

Let $R(G,p)$ denote all-terminal reliability, let $\mathcal{G}_{m-4,m}$ be the class of graphs with $m$ edges and $m-4$ vertices, and let a weak subdivision replace edges by chains…

Boesch–Satyanarayana–Suffel conjecture. The graph $L(r+1,n)$ should attain the minimum of $R_G(p)$ among all connected simple graphs with $r+1$ vertices and $n$ edges.

Let $\mathcal C_{n,m}$ be the class of connected simple graphs on $n$ vertices and $m$ edges, and define its corank by $c=m-n+1$. A uniformly most reliable graph (UMRG) is a graph…

Let $n\re1$, set $m=n+5$, and let a graph be $p$-optimal if it maximizes all-terminal reliability $R(G,p)$ among $(n,m)$-graphs. A balanced weak subdivision of the Petersen graph i…

Let $K_{3,3}$ be the complete bipartite graph with three vertices in each part, and obtain weak subdivisions by replacing its edges with chains. A uniformly most reliable graph (UM…

Let $G$ be a multigraph with $n$ vertices and $m$ edges, and call $G$ uniformly optimal if it maximizes the all-terminal reliability $R(G,p)$ for every percolation parameter $p$. C…

Let $G$ be a multigraph with $n$ vertices and $m$ edges, and call $G$ uniformly optimal if it maximizes the all-terminal reliability $R(G,p)$ for every percolation parameter $p$. F…

Boesch et al.'s conjecture. All UMRGs of corank $4$ are the $4$-wheel and certain subdivisions of the complete bipartite graph $K_{3,3}$.

Ath and Sobel's conjecture. If a nonempty class $\mathcal C_{n,m}$ has corank $c\in\{5,6,7,8\}$ and $n\geq 2c-2$, then $\mathcal C_{n,m}$ contains at least one UMRG.

Boesch's conjecture. If $\mathcal C_{n,m}$ is nonempty, then it contains at least one UMRG.

Let $p$ be the node-failure probability, and let $n$ be the order of a strongly connected digraph with $2n$ arcs. Consider the directed circulant graphs described in the paper: for…

Heawood and Möbius–Kantor UMRG conjecture. The Heawood graph and the Möbius–Kantor graph belong to the set of uniformly most-reliable graphs.

The $(n,n+3)$-UMRG conjecture. For every $n>6$, all uniformly most-reliable $(n,n+3)$-graphs are elementary subdivisions of $K_{3,3}$.