Most switching classes with primitive automorphism groups contain graphs with trivial groups

zbMATH Open1321.05105arXiv1407.5288MaRDI QIDQ2947384

P. J. Cameron, Pablo Spiga

Publication date: 23 September 2015

Abstract: The operation of switching a graph $Gamma$ with respect to a subset $X$ of the vertex set interchanges edges and non-edges between $X$ and its complement, leaving the rest of the graph unchanged. This is an equivalence relation on the set of graphs on a given vertex set, so we can talk about the automorphism group of a switching class of graphs. It might be thought that switching classes with many automorphisms would have the property that all their graphs also have many automorphisms. However the main theorem of this paper shows a different picture: with finitely many exceptions, if a non-trivial switching class $mathcalS$ has primitive automorphism group, then it contains a graph whose automorphism group is trivial. We also find all the exceptional switching classes; up to complementation, there are just six.

Full work available at URL: https://arxiv.org/abs/1407.5288

zbMATH Keywords

automorphism group

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (1)

Most primitive groups are full automorphism groups of edge-transitive hypergraphs.

Uses Software

• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Most switching classes with primitive automorphism groups contain graphs with trivial groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947384)