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.

### Like this:

Like Loading...

*Related*

## Leave a Reply