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.


  • 4
    $\begingroup$ What is a local complementation operation? $\endgroup$ – aaron Feb 25 '11 at 20:12
  • 2
    $\begingroup$ 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. $\endgroup$ – Tom De Medts Feb 26 '11 at 12:41
  • $\begingroup$ Okay, thanks. This is an interesting question. $\endgroup$ – aaron Feb 26 '11 at 19:31
  • $\begingroup$ 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? $\endgroup$ – P.H. Feb 26 '11 at 21:11

This is not really an answer, but I strongly suspect that Theorem 14 in

Transitivity of local complementation and switching on graphs Andrzej Ehrenfeucht , a, Tero Harju , b and Grzegorz Rozenberg , c

(discrete mathematics 2004)

Is fairly close to what you need.

  • 1
    $\begingroup$ Thanks for this comment. I had seen that paper, however we haven't been able to adapt their techniques for this more restricted case. The switching allows one (along with local complementation) to span all possible graphs on v vertices. The proof in that paper relies heavily on this fact. For LC alone however one is limited to subsets of all the graphs, and as far as I known there is no efficient method of calculating the number of graphs in an LC-orbit. I suspect this is part of the reason why this problem may be difficult to answer. $\endgroup$ – P.H. Feb 27 '11 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.