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 ${E\Gamma}$ and arc set ${A\Gamma}$.

A graph ${\Gamma}$ is called edge-transitive if ${\mathrm{Aut}(\Gamma)}$ acts transitively on the set of edges of ${\Gamma}$ and is called arc-transitive if ${\mathrm{Aut}(\Gamma)}$ 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 ${G}$ be a transitive permutation group on a set ${\Omega}$. The orbits of ${G}$ on ${\Omega\times\Omega}$ are called orbitals. An orbital ${\mathcal{O}}$ is called self-paired if for all ${(\alpha,\beta)\in \mathcal{O}}$ the element ${(\beta,\alpha)}$ also lies in ${\mathcal{O}}$. This is equivalent to there being an element ${g\in G}$ that interchanges ${\alpha}$ and ${\beta}$. For each self-paired orbital we can construct a graph ${\Gamma}$ with vertex set ${\Omega}$ and edges ${\{\alpha,\beta\}}$ for all ${(\alpha,\beta)\in \mathcal{O}}$. The group ${G}$ is an arc-transitive group of automorphisms of ${\Gamma}$. Moreover, all arc-transitive graphs arise in this way.

John claims that he and Gordon are confused by the various adjectives used by us graph symmetry people and how they relate to each other so I have decided to write some posts outlining the main ones and their importance. There is a nice diagram on wikipedia illustrating the relationship between the main ones and I will use that as the basis of my discussion.

Throughout I will use ${\Gamma}$ to denote a graph and ${G}$ to denote a group (unfortunately some authors use the reverse.) All graphs will be simple (that is, undirected, no multiple edges, and no loops) and finite. The full automorphism group of a graph, that is the group of all permutations of the set of vertices that take edges to edges, will be denoted by ${\mathrm{Aut}(\Gamma)}$. I will use ${V\Gamma}$ to denote the set of vertices, ${E\Gamma}$ to denote the set of edges and ${A\Gamma}$ to denote the set of arcs, that is the set of ordered pairs of adjacent vertices.

The first adjective is regular. A graph is called regular if each vertex has the same number of neighbours. This number is referred to as the valency of the graph.

A graph is called vertex-transitive if ${\mathrm{Aut}(\Gamma)}$ acts transitively on the set of vertices, that is, for all ${v, u\in V\Gamma}$ there exists an automorphism ${g}$ such that ${u^g=v}$. Sometimes we wish to restrict our attention to a subgroup ${G}$ of ${\mathrm{Aut}(\Gamma)}$ and say that ${\Gamma}$ is ${G}$-vertex-transitive if ${G}$ acts transitively on ${V\Gamma}$.

One consequence of a graph being vertex-transitive is that it is regular: if an automorphism ${g}$ maps ${u}$ to ${v}$ then it also maps the neighours of ${u}$ to the nieghbours of ${v}$. However, not all regular graphs are vertex-transitive. In fact, it is even possible for a regular graph to have a trivial automorphism group, for example, the Frucht graph.

I’ve just uploaded a new version of a paper on graphs with integer flow roots to the arxiv. This is a joint paper with the matroid theorist Joe Kung from University of North Texas.

It is basically a dual version of the old problem of characterising graphs whose chromatic polynomials have integer roots. Chordal graphs, which are built up from a single vertex by repeatedly adding a new vertex adjacent to a clique, are one such class of graphs. But there are lots of non-chordal examples, and it seems hopeless to try and classify them all.

We considered the dual problem of the graphs whose flow polynomials have integer roots. Again there is an obvious class of examples, namely the planar duals of chordal graphs, but in this case there are no other examples. So the punchline of our paper is that “the obvious examples are the only examples”.

In matroid terms, the result says that a cographic matroid with integer characteristic roots is necessarily supersolvable.

We needed the new version because a student at MIT, Maria Monks, spotted a (fixable) error in the first version. This was despite the paper having been refereed and accepted already! So the power of the arxiv has saved Joe and I some red faces.