8
$\begingroup$

Note: this is fixed in version 10.

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.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Szabolcs
    Commented Mar 28, 2013 at 14:57
  • $\begingroup$ @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... $\endgroup$
    – PlatoManiac
    Commented Mar 28, 2013 at 15:03
  • $\begingroup$ << Combinatorica; graph1 = Cycle[8, Type -> Undirected]; VertexConnectivity @graph1` always worked :D $\endgroup$
    – Dr. belisarius
    Commented Mar 28, 2013 at 21:02
  • 1
    $\begingroup$ @belisarius Unfortunately Combinatorica is not too speedy because it's implemented purely in Mathematica. $\endgroup$
    – Szabolcs
    Commented Apr 21, 2013 at 2:06

2 Answers 2

Reset to default
8
$\begingroup$

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`"]].

Improve this answer
$\endgroup$
4
$\begingroup$

EDIT

An easier way is using this package. Tutorial here.

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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