I’m trying to generate a list of all local complements of a graph $ G$ . A local graph complement $ G\star v$ for $ v\in V$ is defined as taking the neighbourhood of the vertex $ v$ , and flipping the existence of any edge within that neighbourhood.

I have the following Mathematica code.

`LocalComplement[g_Graph,v_]:=LocalComplement[g,v]=With[{ h=VertexDelete[NeighborhoodGraph[g,v],v] }, GraphUnion[GraphDifference[g,h],GraphComplement[h]] ] AllLocalComplements[g_Graph]:=AllLocalComplements[g]=AllLocalComplements[g,{g}] AllLocalComplements[g_Graph,list_List,excludedVertices_List:{}]:=AllLocalComplements[g,Sort@list,Sort@excludedVertices]=Fold[AllLocalComplements[g,#1,#2]&,list,Complement[VertexList@g,excludedVertices]] AllLocalComplements[g_Graph,list_List,v_]:=With[{ lcg=LocalComplement[g,v] }, If[ MemberQ[list,gg_/;IsomorphicGraphQ[lcg,gg]], list, AllLocalComplements[lcg,list~Join~{lcg},{v}] ] ] `

The algorithm is correct; however, starting at $ n>6$ vertices (depends a bit on the graph, but definitely for $ n=9$ ) there is a `$ RecursionLimit=1024 exceeded`

error cropping up. I suspect this is because of the `Fold[AllLocalComplements...`

-call, which is highly recursive.

My questions:

- Can MM somehow optimize this using tail recursion? And if not, is there a way of writing this in a MM-esque way? I know I can do it with
`For`

-loops etc. but that wouldn’t be as pretty. - Can you give me advice on how to improve performance of the code?

Thanks a lot!

~ JB