Implementing local complements of graphs

Question

I'm trying to write a routine which generates the local complement of a graph at a vertex. For those who don't know, the local complement for a singly-connected, undirected graph is defined as the graph where for all vertices adjacent to the selected one, two of them have an edge exactly if they don't have in the original one (in other words, the subgraph containing only the adjacent edges). All other edges, including those connecting the selected vertex with its adjacent vertices, are unchanged.

For example,

LocalComplement[Graph[{1 <-> 2, 2 <-> 3, 3 <-> 1}], 1]

should give

Graph[{1 <-> 2, 3 <-> 1}]

and

LocalComplement[Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 1}], 1]

should give

Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 1, 2 <-> 4}]

Here's what I've tried:

LocalComplement[g_,v_]:=Module[{h=VertexDelete[NeighborhoodGraph[g,v],v]},
  GraphUnion[GraphDifference[g,h],GraphComplement[h]]]

The idea is simple: First I determine the neighbourhood of the selected vertex. Since Mathematica includes the vertex in the NeighborhoodGraph, I remove that. Then I remove the original subgraph h from g and add the complement of h.

This works well with the first example above, but for the second example, the same graph is returned, without the additional edge. Therefore I'd like to know:

• Why does my code not work as expected?
• And of course: How can I fix it?

Answer 1

For your two examples

g1 = {1 <-> 2, 2 <-> 3, 3 <-> 1}; g2 = {1 <-> 2, 2 <->3, 3 <-> 4, 4 <-> 1};

your function LocalComplement[_,_] gives the results:

EdgeList[LocalComplement[Graph[g1], 1]] (*  gives {1 <-> 2, 3 <-> 1} *)

and

EdgeList[LocalComplement[Graph[g2], 1]] (* gives {1 <-> 2, 2 <-> 3, 2 <-> 4, 
     3 <-> 4, 4 <-> 1}

which are both correct.

For pictures, using

 gplt:={Graph[#, VertexShapeFunction -> "Name"], 
   Graph[EdgeList[LocalComplement[Graph[#], 1]],VertexShapeFunction -> "Name"]} &

for the two examples, I get

 gplt@g1  (* gives *)

and

gplt@g2  (* gives *)

EDIT: Graph is introduced with version 8.0, and specific details of "over 500" fixes and improvements from V8.0 to V8.0.4 has not been released. Since your function works fine in V8.0.4 but gives incorrect results in V8.0, it is likely that you are seeing the effect of a bug that has been fixed in 8.0.4.