Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.