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 of recognizing LC-equivalence, in 10.1007/BF01275668. But if there's an efficient enumeration instead of removing duplicates I'd be happier. Thanks! $\endgroup$