2
$\begingroup$

I want to know the vertex connectivity of a random graph on (say) 4 vertices. I can get the vertex connectivity of each of the 11 graphs on 4 vertices with this:

Table[GraphData[{4, k}, "VertexConnectivity"], {k, 1, 11}]

If we label these 11 graphs we have 64 labeled graphs. In particular, the two unlabeled graphs with connectivity 2 have 3 + 6 = 9 labelings. I was expecting the vertex connectivity of 2 to appear with probability 9/64 in:

Table[VertexConnectivity[RandomGraph[BernoulliGraphDistribution[4, 0.5]]], {1000}]

However, I do not obtain this probability form the above calculation. I am using Mathematica 9.0.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Is this a math question or a Mathematica one? You seem to have the answer to the question in the title. Are you asking why you don't get 9/64? It seems to me that you are getting ratios close 9/64. So what is the question then? $\endgroup$ Commented Oct 11, 2016 at 9:56
  • 1
    $\begingroup$ If you have v9, be aware that VertexConnectivity is buggy. mathematica.stackexchange.com/q/22261/12 $\endgroup$ Commented Oct 11, 2016 at 10:54
  • $\begingroup$ I AM using version 9. I am NOT getting ratios that are close to 9/64. In fact, I am not getting any 2's at all from the above code. Are you saying version 9 does not work correctly? $\endgroup$ Commented Oct 11, 2016 at 14:56
  • $\begingroup$ See the link from my comment, the details (which I don't all remember) are in there. All I remember is that sometimes VertexConnectivity would return incorrect answers in v9. This is fixed in v10.0+. $\endgroup$ Commented Oct 11, 2016 at 15:00
  • $\begingroup$ In version 11.0, Count[Table[ VertexConnectivity[ RandomGraph[BernoulliGraphDistribution[4, 0.5]]], {10000}], 2]/10000. returned 0.14. In v9 I get 0. v9 is definitely buggy. $\endgroup$ Commented Oct 11, 2016 at 18:47

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.