Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.