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$
11
  • $\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$ Commented Nov 22, 2018 at 1:38
  • $\begingroup$ That's already an excellent idea. That sped it up by a factor of 10. $\endgroup$
    – J Bausch
    Commented Nov 22, 2018 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
    Commented Nov 22, 2018 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$ Commented Nov 22, 2018 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
    Commented Nov 23, 2018 at 19:40

0

You must log in to answer this question.