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 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 has valency k then for each the number of vertices of at distance i from a vertex v is . Hence for g odd we have
The number of vertices at distance i from an edge is for each . Hence for 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 , 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.