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?