1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Brendan McKay Nov 22 '18 at 1:38
  • $\begingroup$ That's already an excellent idea. That sped it up by a factor of 10. $\endgroup$ – J Bausch Nov 22 '18 at 10:47
  • $\begingroup$ 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! $\endgroup$ – J Bausch Nov 22 '18 at 11:02
  • $\begingroup$ 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? $\endgroup$ – Brendan McKay Nov 22 '18 at 12:37
  • $\begingroup$ 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? $\endgroup$ – J Bausch Nov 23 '18 at 19:40

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.