I described here how Pablo Spiga and I showed that all but finitely many nontrivial switching classes of graphs with primitive automorphism group contain a graph with trivial automorphism group, and found the six exceptions. (The *trivial* switching classes are those containing the complete and null graphs.)

Being in Prague makes me think about graph homomorphisms, so I wondered:

**Problem** Is it true that all but finitely many nontrivial switching classes of graphs with primitive automorphism group contain a *rigid* graph (one with trivial endomorphism monoid)?

The difficulty seems to be that homomorphisms privilege edges over nonedges (edges must map to edges, but non-edges can be collapsed or mapped to edges or nonedges), whereas switching treats edges and nonedges on the same footing. I can’t see how to begin: what possible connection exists between the endomorphism monoids of graphs related by switching?

(And yet, switching classes are equivalent to double covers of complete graphs, which are certainly things with a homomorphism-like feel to them.)

On the subject of switching, I managed to show the analogue for tournaments of the result for graphs. There are no “trivial” tournaments (admitting the symmetric group), so the result is:

**Theorem** With two exceptions (on 4 and 8 vertices), a switching class of tournaments with primitive automorphism group contains a tournament with trivial automorphism group.

This is much easier than the result for graphs. While any permutation group preserves a switching class of graphs, the groups preserving switching classes of tournaments are much more restricted: the Sylow 2-subgroups are cyclic or dihedral and act semiregularly. The only primitive groups occurring are groups of odd order (and odd degree), and groups between PSL(2,*q*) and PΣL(2,*q*), where *q* is a prime power congruent to 3 (mod 4).

### Like this:

Like Loading...

*Related*

##
About Peter Cameron

I count all the things that need to be counted.