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 *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 *k *then for each *i *from a vertex *v *is *g *odd we have

The number of vertices at distance *i *from an edge is *g* even we get

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*-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.

Given a group *G *and subset *S* such that *Cayley graph Cay(G,S), * is the graph with vertices the elements of G and two elements *x *and *y *are adjacent if and only if *G *acts transitively by right multiplication on the vertices of our Cayley graph and preserves adjacency. Thus we obtain a regular group of automorphisms. Indeed a graph

Note that the neighbours of *Cay(G,S) *are the elements of *S *and the neighbours of an element *x *are the elements *sx*, for *Cay(G,S) *is vertex-transitive it is sufficient to find such a cycle starting at *s* by multiplying together the elements of S labelling the edges of the cycle. This path will be a cycle if the word is equal to

Now for the construction of Biggs: take a tree *T *of depth *g*-1 such that all vertices at depth less than *g-1 *have valency *k*. Colour the edges of *T* with *k *colours so that no two edges adjacent to a common vertex have the same colour. For each colour *T *such that *v *and *w *if and only if *v* and *w *are joined by an edge coloured *S *be the set of* k *involutions obtained and *G *be the group generated by *S *(*G *is finite as it is a group of permutations of a finite set). Then *Cay(G,S) *is a *k*-regular graph. Now if the girth of our Cayley graph was *T *under *s<g *from the root, contradicting *Cay(G,S) *has girth at least *g*.

Cayley graphs have been used to construct cages and also for some values of *(k,g) *give graphs with the lowest known number of vertices. For example the smallest known graph of valency 3 and girth 13 is a Cayley graph for AGL(1,17). If you want to construct a Cayley graph of valency k and girth g the general idea is to find a group with k generators such that no word of length less than *g *in the generators evaluates to the identity. One thing to note here is that a Cayley graph of an abelian group has girth at most four as for any two elements *x, y* in the group,

Another method that has been fruitful in constructing cages or graphs holding the record is voltage assignments. We start with a multigraph *k*, and a group *G*. The graph *base graph *and *G* the *voltage group*. A *voltage assignment *is a labelling of the arcs of *G *such that if an arc is labelled by *g* then the reverse arc is labelled by *lift *of *(v,g)* is adjacent to *(w,h) *if and only if *v* is adjacent to *w *in *v *to *w *is labelled by *G *acts semiregularly as a group of automorphisms of the lift as an element *(v,g) *to *(v,gk).*

For an example, let *u* and *v* joined by a single edge and with a loop on each vertex. We use *u *and *v *by 0, the loop at *u *by 1 and the loop at *v *by 2. The vertices of the lift are all pairs *(u,i) *and *(v,i) *with *(u,i) *is adjacent to *(u,j) *when *(v,i) *is adjacent to *(v,j)* when *(u,i) *is adjacent to *(v,i). *You may recognise this graph as the Petersen graph.

Next I discuss the notion of a family with large girth due to Biggs. Our discussion is along the lines of the Dynamic Survey. Using the Moore bounds, we see that the least number of vertices of a *k*-regular graph of of girth *g *is roughly *k*-regular graph of girth *g *we have *k*-regular graphs with girth *family with large girth *if there is a constant