Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

As I noticed in the documentation VertexConnectivity is defined as the following

The vertex connectivity of a graph $g$ is the smallest number of vertices whose deletion from $g$ disconnects $g$.

Now for a CycleGraph I expect one needs to delete at least two vertices to make the resulting graph disconnected. Please correct me if I am driven by a wrong intuition here.

opt = {VertexLabels -> "Name", ImagePadding -> 10};
graph1 = CycleGraph[8, opt];
graph2 = UndirectedGraph[Graph[{1 -> 3, 1 -> 7, 1 -> 10, 2 -> 5, 2 -> 6, 3 -> 6,
3 -> 10,4 -> 7, 4 -> 8, 4 -> 9, 5 -> 9, 6 -> 10, 7 -> 8, 8 -> 9}],opt];
Row[{graph1, graph2}]

enter image description here

Strange!

Now Mathematica is returning this not so intuitive values for the graph1 and graph2.

VertexConnectivity /@ {graph1, graph2}

{1,1}

How can one make any of these above graphs disconnected by deleting just one vertex? Can someone shade some light on this issue? EdgeConnectivity though gives understandable output for both the graphs.

share|improve this question
1  
I think this is clearly a bug. Can you please report it? This would surely bite me too sooner or later. The graph-related functions seem to have more bugs than usual. –  Szabolcs Mar 28 '13 at 14:57
    
@Szabolcs I feared the same! This type of bugs can really make the overall graph functionality very much unstable and unreliable in nature. I will wait a bit as some WRI guys are active here as well...they may comment meanwhile... –  PlatoManiac Mar 28 '13 at 15:03
    
<< Combinatorica; graph1 = Cycle[8, Type -> Undirected]; VertexConnectivity @graph1` always worked :D –  belisarius Mar 28 '13 at 21:02
    
@belisarius Unfortunately Combinatorica is not too speedy because it's implemented purely in Mathematica. –  Szabolcs Apr 21 '13 at 2:06

2 Answers 2

This was confirmed by support to be a bug.


One workaround is to use Combinatorica`VertexConnectivity:

graph1 = CycleGraph[8];
graph2 = UndirectedGraph[
   Graph[{1 -> 3, 1 -> 7, 1 -> 10, 2 -> 5, 2 -> 6, 3 -> 6, 3 -> 10, 
     4 -> 7, 4 -> 8, 4 -> 9, 5 -> 9, 6 -> 10, 7 -> 8, 8 -> 9}]];

Block[{$ContextPath},
 Needs["Combinatorica`"];
 Needs["GraphUtilities`"]
 ]

Combinatorica`VertexConnectivity@
   GraphUtilities`ToCombinatoricaGraph[#] & /@ {graph1, graph2}

See here for the purpose of Block around Needs.


P.S. It turns out that the GraphUtilities`ToCombinatoricaGraph function re-adds Combinatorica to the context path every time it's called. If you prefer not to have Combinatorica in the context path, you can consider editing GraphUtilities.m and changing Needs["Combinatorica`"] to Block[{$ContextPath}, Needs["Combinatorica`"]].

share|improve this answer

EDIT

An easier way is using this package

IGraph["vertex.connectivity"][CycleGraph[5]]

(* ==> {.2} *)

Old version

As a workaround, you can access igraph through RLink. Once igraph is installed (install.packages(igraph)) and loaded (library(igraph)), do this:

vertexConnectivity[g_?GraphQ] := 
 Round@First@RFunction["function (e) {
        g <- graph.edgelist(e,directed=F);
        vertex.connectivity(g)
     }
     "][List @@@ EdgeList[g]]

vertexConnectivity[CycleGraph[8]]

(* ==> 2 *)

See also here on how to access igraph through RLink.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.