# Generate all connected non-isomorphic graphs of n vertices modulo local complementation?

I'd like to generate a list of all simple, connected, undirected graphs of $$n$$ vertices, modulo standard graph isomorphism, and modulo local complementation, which is the following operation: for a graph $$G=(V,E)$$, mark a vertex $$v\in V$$, and let $$S_v$$ be its neighbourhood (such that $$v\not\in S_v$$). Let $$C_v$$ be a complete graph on the vertices $$S_v$$. Then define $$G'=G\ \mathrm{xor}\ C_v$$, i.e. for any pair of vertices in the neighbourhood of $$v$$, we negate the existence of an edge.

An example of this operation can be seen in fig. 1 in arXiv:0710.2243.

For edge local complementation, there seems to be a way to enumerate all such graphs efficiently, see the number sequence on https://oeis.org/A156800.

I know of the program geng, which gives me all non-isomorphic graphs of $$n$$ vertices. Currently I use it with Mathematica together with a custom comparator that, given a graph $$G_1$$, checks whether it is isomorph to any of all possible local complements of $$G_2$$; unfortunately that is slow due to the extensive use of IsomorphicGraphQ, and because there is a lot of local complements to any given graph.

Does anyone know of a more efficient way of generating said graphs? Maybe directly using something within nauty?

Thanks a lot! - JB

• This sounds difficult. One thing you are probably doing already: make a cheap invariant (eg sum of the squares of the degrees) and only use an isomorphism test if the invariants match. – Brendan McKay Nov 22 '18 at 1:38
• That's already an excellent idea. That sped it up by a factor of 10. – J Bausch Nov 22 '18 at 10:47
• Which makes me wonder if Mathematica doesn't do this by default in IsomorphicGraphQ. There is in fact an efficient way of recognizing LC-equivalence, in 10.1007/BF01275668. But if there's an efficient enumeration instead of removing duplicates I'd be happier. Thanks! – J Bausch Nov 22 '18 at 11:02
• It is an excellent problem. Is this true: if $G$ and $H$ are LC-isomorphic (equivalent by LC and isomorphism), then there are vertices $u$ of $G$, and $v$ of $H$, such that $G-u$ and $H-v$ are LC-isomorphic? – Brendan McKay Nov 22 '18 at 12:37
• That's a good question. I'm not sure; I tried to find a counterexample but couldn't find one. But I also couldn't prove it (yet). Would that imply an effective enumeration? – J Bausch Nov 23 '18 at 19:40