2
$\begingroup$

Is there anything known about the least-reliable simple graphs, among all graphs $G$ with edge-connectivity $c \leq n$?

Here, least-reliable means the lowest all-terminal reliability, i.e. the probability that the graph $G$ remains connected, when edges fail independently with probability $p$

If you don't restrict to simple graphs, then it is known that the cycle graph with $c/2$ edges between successive vertices is the least simple for a fixed value of $c$. But this graph is far from simple.

  • 0
    My intuition says you should make a big circle of the vertices and connect each one to the $\frac c2$ vertices on each side. This comes from the "small world" studies saying a few bridges bring things much closer together. But it is just a guess.2012-08-13

0 Answers 0