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

`IsomorphicGraphQ`

. There is in fact an efficient way ofrecognizingLC-equivalence, in 10.1007/BF01275668. But if there's an efficient enumeration instead of removing duplicates I'd be happier. Thanks! $\endgroup$ – J Bausch Nov 22 '18 at 11:02