# Local complementation group of simple graphs

This is my first time posting a question, so please excuse me for any incomplete or confusing descriptions.

Let's assume we start with one simple graph(no multi-edges and no loops of a vertex to itself), call this $g_1$, on $v$ vertices.
There are exactly $v$ local complementation operations ($lc$) for such a graph. Now let us obtain all possible graphs, by repeated action of the $lc$'s, on $g_1$. This set, by definition is an orbit. Let's assume this results in $k$ graphs (which must be finite). If we number these graphs, $1,\cdots,k$, we see that we can write the associated $lc$'s as permutations. Ex/ $lc_1 =(1,5)(3,8)\cdots$. These $lc$'s therefore form the set of generators for the local complementation group that acts on the $k$ graphs.

The question is, what is this group?

We've done some numerical work on graphs up to and including 6 vertices. Amazingly (unless if there is a trivial reason for this) we always find either $S_k$ (the permutation group) or $A_k$ (the alternating group). We know what causes the distinction; namely whenever all the $lc$ generators are of even length we get $A_k$. In this sense we always get the maximal group on $k$ elements.

Thanks in advance for any help.

P.H.

• What is a local complementation operation? – aaron Feb 25 '11 at 20:12
• The local complementation w.r.t. a given vertex v is the operation that changes the subgraph induced on the neighbors of v (not including v) into its complement. In particular, it is an involution, so the "local complementation group" is a transitive group generated by involutions. – Tom De Medts Feb 26 '11 at 12:41
• Okay, thanks. This is an interesting question. – aaron Feb 26 '11 at 19:31
• Stated in this context, if I'm not mistaken, the question becomes: (if true!)Why is the local complementation group on k graphs (in an lc-orbit), either k-transitive or (k-2)-transitive? – P.H. Feb 26 '11 at 21:11