Skip to main content
3 of 3
added 44 characters in body
P.H.
  • 141
  • 7

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.

P.H.
  • 141
  • 7