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.

Guillermo Pineda-Villavicencio visited Perth from the University of Ballarat for the previous two weeks and introduced me to the cage problem so I thought I would write a post setting out what I have learnt to get it all straight in my mind.

The girth g of a graph $\Gamma$ is the length of the shortest cycle . The cage problem is to find the smallest number n(k,g) of vertices for a regular graph of valency k and girth g. A valency k graph of girth g with n(k,g) vertices is referred to as a (k,g)-cage. A (k,g)-cage is not necessarily unique. In fact there are 18  (3,9)-cages and these have order 58.

The Petersen graph is the (3,5)-cage and has order 10. The Heawood graph, (the point-line incidence graph of the Fano plane) is the (3,6)-cage and has order 14. In fact the point-line incidence graph of a projective plane of order q is a (q+1,6)-cage. The Tutte-Coxeter graph (the point-line incidence graph of the smallest generalised quadrangle W(2)) is the (3,8)-cage and is sometimes called Tutte’s 8-cage.  The point-line incidence graph of a generalised quadrangle of order (q,q) is a (q+1,8)-cage.

The actual value of n(k,g) has only been determined for a small number of values of k and g.  The latest knowledge of bounds on n(k,g) is given in these tables at the Combinatorics Wiki.  There is also a good dynamic survey by Geoffrey Exoo and Robert Jajcay at the Electronic Journal of Combinatorics.

In some sense the cage problem is the opposite to the problem of finding Moore graphs discussed by John in an earlier post which are the extremal graphs for the degree-diameter problem, that is, the problem of finding the largest graphs of a given valency and diameter.

If $\Gamma$ has valency k then for each $i\leq \lfloor \frac{(g-1)}{2}\rfloor$ the number of vertices of $\Gamma$ at distance i from a vertex v is $k(k-1)^{i-1}$. Hence for g odd we have

$n(k,g)\geq 1+k+k(k-1)+k(k-1)^2+\ldots+k(k-1)^{(g-3)/2}$

The number of vertices at distance i from an  edge is $2(k-1)^i$ for each $i\leq\lfloor \frac{(g-1)}{2}\rfloor$. Hence for  g even we get

$n(k,g)\geq 2(1+(k-1)+(k-1)^2+\ldots+(k-1)^{(g-2)/2})$

The graphs which meet these bounds are the Moore graphs mentioned previously. These bounds give us an initial lower bound for n(k,g).

There is a construction of Sachs (Regular graphs with given girth and restricted circuits, J.  London Math. Society 38 (1963) 423-429)  which shows that for all $k,g\geq 3$, there exists a k-regular graph of girth g.   Here I will give a construction of Biggs which shows that there is  a finite k-regular Cayley graph of girth at most g. First I need to discuss Cayley graphs.