# Implementing local complements of graphs

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?
-

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.

-
That's interesting. I get the results I said. To be sure to not have made a copy/paste error which happened to fix the code, I've now copied the code directly from my question to Mathematica, and I again got the result. Maybe it's a bug in my version (8.0.0.0) which got corrected in your version (which version do you use?) –  celtschk Jan 19 '12 at 12:16
I am using V 8.0.4. I think there isa typo in your question: the expected result for the first example should be Graph[{1<->2,3<->1}]. –  kguler Jan 19 '12 at 12:43
Indeed, there was a typo, thanks. I've now fixed that. So I just have to wait until the sysads install the newer version. If you add the information that it's probably a Mathematica bug, I'll accept your answer. –  celtschk Jan 19 '12 at 13:04
@celtschk, I just added a comment that it is probably a 8.0.0 bug fixed in 8.0.4. –  kguler Jan 19 '12 at 13:41