# Least-reliable simple graphs

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.

-
What does "least-reliable" mean (in this context)? – Gerry Myerson Aug 13 '12 at 12:39
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. – Ross Millikan Aug 13 '12 at 13:15