# Graph symmetry II

In my previous post I discussed various measures of symmetry of the vertex set of a graph. The main terms introduced were vertex-transitive, vertex-primitive, vertex-quasiprimitive, vertex-biprimitive and vertex-biquasiprimitive. It was also seen that the class of vertex-transitive graphs was very large and so we often place further symmetry conditions on our graphs so that we can obtain interesting results. In this post I wish to discuss conditions on the symmetry of the edge set and arc set .

A graph is called *edge-transitive* if acts transitively on the set of edges of and is called *arc-transitive* if acts transitively on the set of arcs. As long as there are no isolated vertices (that is vertices with no neighbours) then an arc-transitive graph will also be vertex-transitive and edge-transitive. Such graphs are often called *symmetric*.

I will first discuss how to construct all arc-transitive graphs. Let be a transitive permutation group on a set . The orbits of on are called *orbitals*. An orbital is called *self-paired* if for all the element also lies in . This is equivalent to there being an element that interchanges and . For each self-paired orbital we can construct a graph with vertex set and edges for all . The group is an arc-transitive group of automorphisms of . Moreover, all arc-transitive graphs arise in this way.

The orbitals of correspond to the orbits of on . These orbits are called *suborbits* and we call a suborbit *self-paired* if its corresponding orbital is self-paired. The length of the suborbit is equal to the valency of the corresponding orbital graph. Thus studying arc-transitive graphs of valency is the same as the study of transitive permutation groups with a self-paired suborbit of size .

If we assume that an arc-transitive graph is also vertex-primitive then it is possible to deduce a few things. The Sim’s conjecture (proved by Cameron, Praeger, Saxl and Seitz with the aid of the Classification of Finite Simple Groups) states that there exists a function such that given a primitive group with a suborbit of size , the order of the point stabiliser has order at most . So the order of a vertex stabiliser for a vertex-primitive, arc-transitive graph is bounded. This gives us some hope of classifying all vertex-primitive, arc-transitive graphs of a given valency. Indeed in 1967, Wong showed that there is one infinite family and 4 sporadic examples of vertex-primitive, arc-transitive graphs of valency 3. More recently in 2004, Cai Heng Li, Zai Ping Lu and Dragan Marusi\v{c} showed that there are 5 infinite families and 5 sporadic examples of vertex-primitive, arc-transitive graphs of valency 4.

Now not every edge-transitive and vertex-transitive graph is also arc-transitive. Edge-transitive, vertex-transitive but not arc-transitive graphs are called *half-arc-transitive* or sometimes *half-transitive*. Such graphs have been the focus of a large amount of research. The smallest one is the Holt graph on 27 vertices and valency 4. Half-arc-transitive graphs must have even valency and in 1970, Bouwer showed that one exists for every even valency . Given a transitive group with a nonself-paired orbital we can construct a graph upon which is vertex- and edge-transitive but not arc-transitive on by taking the edges to the be pairs such that or lies in the orbital. However, may not be the full automorphism group of and so may be arc-transitive. Thus finding half-arc-transitive graphs is more complicated than just finding transitive groups with a nonself-paired orbital.

Whereas every connected arc-transitive graph is vertex-transitive, not every edge-transitive graph is vertex-transitive. For example, the Gray graph. If a graph is edge- but not vertex-transitive then the automorphism group has two orbits on vertices and the graph is bipartite with the two bipartite halves being the two orbits. Such graphs need not be regular but if they are we call them *semisymmetric*. The Gray graph is semisymmetric. Again semisymmetric graphs have been a focus of much investigation and are comparatively rare. Ivanov and Iofinova determined all semisymmetric graphs of valency three whose automorphism group acts primitively on each of its orbits on vertices in 1985. There are only 6 such graphs.

Every edge-transitive bipartite graph can be constructed as follows: Let be a group with subgroups and . The vertices will be the cosets of in and the cosets of in . The edges are the pairs such that . The group acts by right multiplication on both sets of cosets and maps edges to edges so induces a group of automorphisms of that has two orbits on vertices. Moreover, is edge-transitive since if then maps the edge to . Now not all automorphisms of may be induced by . Indeed if is regular there are often automorphisms that interchange the bipartite halves. Trying to prevent the existence of such automorphisms is what makes it harder to construct semisymmetric graphs.

I can now give the Venn diagram for this post.

To end this post I will say a few words about local symmetry properties. Given some symmetry propery , we say that a graph is *locally * if for each vertex , the vertex stabiliser has property in its action on the set of neighbours of . For example, we say that a graph is *locally transitive* if for all vertices , acts transitively on . If is connected then every locally transitive graph is edge-transitive. Not every edge-transitive graph is locally transitive, for example half-arc-transitive graphs are edge-transitive but not locally transitive.

Another useful local property is being *locally primitive*. This property is important when studying quotients of graphs. Moreover, since any transitive group on a prime number of points is primitive, any arc-transitive graph of prime valency is locally primitve.

Given a graph and a partition of the vertex set then the quotient graph is the graph with vertex set the parts of and two parts are adjacent if there exists and such that and are adjacent in . If is preserved by then induces automorphisms of . Moreover, if is locally primitive then is a *cover* of , that is for each pair of adjacent parts of the partition the subgraph of induced between them is a perfect matching. This implies that has the same valency as . Furthermore, the covering property often implies that a family of graphs in preserved under the quotienting operation, that is inherits particular symmetry properties of . This provides a strategy for studying the orginal family, that is, first study all “basic graphs” in the family (those with no meaningful quotients) and then study how to lift these basic graphs to other graphs in the family.

Vertex-transitive, locally quasiprimitive graphs have received some attention (particularly in a paper by Cai Heng Li, Cheryl Praeger, Akshay Venkatesh and Sanming Zhou). The quotienting process for these graphs is not quite as advantageous as here is merely a *multicover* of , that is, instead of a perfect matching between adjacent blocks we get a regular bipartite graph.

I plan one more post in this series where I will discuss some of the more restrictive graph symmetry properties such as distance-transitive and -arc transitive.