Last week I was at the 8th Slovenian Conference on Graph Theory. This was the latest in what is commonly known as the ‘Bled conference’ but this year was in Kranjska Gora. This meant that the conference excursion was to Lake Bled. It was a very enjoyable conference with lots of interesting talks and it was good to catch up with lots of people. I was one of the plenary speakers and my talk was entitled ‘Bounding the number of automorphisms of a graph’. This surveyed the recent work on the Weiss conjecture and its generalisation the PSV conjecture. It also discussed my recent work with Luke Morgan on the PSV conjecture for semiprimitive groups with a nilpotent regular normal subgroup. More details can be found on my slides.
A graph is called vertex-transitive if for every pair of vertices there is an automorphism of the graph that maps the first to the second. I discussed such graphs and other symmetry classes of graphs in two earlier posts. (I see that I had promised a third in that series but that has yet to eventuate.)
A cubic graph is a graph for which every vertex has valency three, that is, every vertex has exactly three neighbours. Cubic graphs have been extensively investigated with many graph properties first investigated in the cubic case. For example, s-arc-transitive graphs were first investigated in the cubic case in the seminal work of William Tutte in two papers in 1947 and 1959.
An arc of a graph is an ordered pair of adjacent vertices and we say that a graph is called arc-transitive if the automorphism group of the graph acts transitively on the set of arcs. The most famous example is the Petersen graph. Arc-transitive graphs are also called symmetric graphs. Ronald Foster began compiling a list of symmetric cubic graphs in 1932 and this is now known as the Foster census. Marston Conder and Peter Dobcsanyi extended the census so that it was complete for graphs with at most 768 vertices and Marston has extended it further to include all graphs with at most 2048 vertices. The graphs are available on Marston’s website.
For vertex-transitive cubic graphs there is data collated by Gordon and Brendan McKay that is complete for all graphs with up to 94 vertices as well as all graphs with n vertices for many values of n at most 258. Recently, Primoz Potocnik, Pablo Spiga and Gabriel Verret have comprehensively smashed this upper bound by compiling a list of all vertex-transitive cubic graphs with at most 1280 vertices. This continues the excellent work in graph symmetry that they have been doing in recent years. They have set up a webpage containing the data and a preprint is on the arxiv explaining their methods. I am sure it will be a valuable resource for investigating graphs and testing conjectures. They have already checked that apart from the four known exceptions they each have a Hamiltonian cycle.
As part of their work they have also compiled a list of all arc-transitive graphs of valency 4 on at most 640 vertices. That is also available on their webpage. Primoz is also undertaking a project with Steve Wilson aiming to list all edge-transitive valency 4 graphs on up to 512 vertices. The data so far is available here.
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.