7
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ What is a local complementation operation? $\endgroup$
    – aaron
    Commented Feb 25, 2011 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
    Commented Feb 26, 2011 at 12:41
  • $\begingroup$ Okay, thanks. This is an interesting question. $\endgroup$
    – aaron
    Commented Feb 26, 2011 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.
    Commented Feb 26, 2011 at 21:11

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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.
    Commented Feb 27, 2011 at 7:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .