Cages of higher valency

This site is designed to help co-ordinate efforts to find the smallest graphs of given valency and girth. If you can beat any of the records listed below, then please e-mail gordon@cs.uwa.edu.au

The case where the valency is 3 is of special interest, so there is a separate page devoted to cubic cages.

Table of Contents

• Introduction
• The known examples (and the table)
• Notes

Introduction

A (k,g)-cage is a k-regular graph of girth g with the fewest possible number of vertices.

Simply counting the numbers of vertices in the distance partition with respect to a vertex yields a lower bound n(k,g) on the number of vertices in a cage, with the precise form of the bound depending on whether g is even or odd.

If g is odd, then

Any cage that actually meets these bounds is very special indeed - a Moore graph if g is odd and a generalized polygon if g is even. However these bounds are met very infrequently and in general we know little about the structure or even the number of vertices in a cage. For girth 3 the complete graphs always meet the Moore bound, and for girth 4 the complete bipartite graphs (generalized digons) always meet the Moore bound.

The values of the smaller Moore bounds for girth at least 5 are given in the following table.

Known examples

There is surprisingly little known about the true size of cages, reflecting our general ignorance of the behaviour of the function n(k,g). We know a little bit about the possibility of graphs meeting the Moore bound precisely, and almost nothing else.

Generalized polygons

For certain even values of the girth the answer is well known. For girth 3 the complete graph on k+1 vertices is the unique cage, while for girth 4 the complete bipartite graph on 2k vertices (a generalized digon) is the unique cage. For girth 6, the Moore bound is met by generalized triangles of order k-1, which are the point/line graphs of projective planes. This therefore occurs whenever k-1 is a prime power, and as far as we know never occurs otherwise. For girth 8, the Moore bound is met by generalized quadrangles (more specifically, the point/line graph of the geometry) of order k-1, which again are known to exist whenever k-1 is a prime power. For girth 12, the Moore bound is met by generalized hexagons of order k-1, which again are known to exist whenever k-1 is a prime power.

Moore graphs

For girth 5, the Moore bound can be met by the Petersen graph on 10 vertices, the Hoffman-Singleton graph on 50 vertices or a possible 3250 vertex graph of valency 57, whose existence is uncertain.

The best of the rest

This table indicates the current state-of-the-art. Each number is a link to an actual graph of the stated size; this is the currently smallest known such graph. A number that is not a link is the size, but the graph is not currently available. Values that are known to be accurate - in almost all cases because they either meet the Moore bound or are small enough that exhaustive searches have been done are preceded by an = sign. The bracketed references after each number give an explanation for the entry (not for the Moore bounds of course). There are no references/explanations for the cubic graphs because they have their own page.

The format for the given graphs is either graph6 or sparse6, which are two formats devised by Brendan McKay. We supply a graph reader that can read a file of graphs in either format (or both formats) so any reader should easily be able to recover the graphs.

Additional Notes

Small cases

The small cases are all well known, but for completeness we will incorporate the descriptions. This essentially follows the various well-known descriptions in the literature, but corrects some errors that seem to have sneaked in.

The girth 5 case

The (4,5)-cages has 19 vertices, and there is a unique cage called the Robertson graph. The automorphism group of the Robertson graph has size 24 and it has 3 orbits of size 3, 4 and 12 respectively.

There are precisely 4 (5,5)-cages on 30 vertices. Unfortunately the descriptions in Wong's survey AND Brouwer, Cohen and Neumaier's book are both incorrect.

The first (5,5)-cage (in our listing) is the Robertson-Wegner graph, which has an automorphism group of size 120. Brouwer gives a nice new description of it in the errata for their book. The Robertson-Wegner graph has 2 orbits, of sizes 10 and 20 respectively. In Wong's survey it is presented as Figure 5, whereas it is actually isomorphic to the graph in Figure 4.

The second (5,5)-cage is a graph induced by 3 pentagons and 3 pentagrams in the 5 pentagon + 5 pentagram description of the Hoffman-Singleton graph. This graph has an automorphism group of size 20 with four orbits of sizes {5,5,10,10}. In Wong's survey it is presented as Figure 4, whereas it is actually isomorphic to the graph in Figure 5.

The third (5,5)-cage is a graph constructed by Foster, with an automorphism group of size 30 and orbit sizes {15,15}. It is given in Wong's survey as Figure 6.

The fourth (5,5)-cage has an automorphism group of order 96 and two orbits of length {6,24}. It was first claimed by Yang and Zhang in 1989 that this completed the collection of (5,5)-cages, and this has since been reconfirmed by Markus Meringer's genreg program.

The presentations for the first three (5,5)-cages are those given in Wong's survey, and the fourth is an arbitrary representative.

There is a unique (6,5)-cage on 40 vertices, obtained by deleting a pentagon and a pentagram from the Hoffman-Singleton graph. It has an automorphism group of size 480 and is transitive.

There is a unique (7,5)-cage on 50 vertices, namely the Hoffman-Singleton which is a Moore graph. It is a transitive graph with an automorphism group of size 252000. The presentation given here is the 5 pentagon + 5 pentagram description from Wong's paper. So vertices {0..4} are the first pentagon, {5..9} the first pentagram, {10..14} the second pentagon etc.

The smallest (8,5)-graph currently known has 80 vertices, and was discovered by myself (Gordon Royle); it has automorphism group of size 160, and is a Cayley graph.

The smallest (9,5)-graph is from an old construction that is variously attributed to Brown, Murty and O'Keefe & Wong. Close examination of the papers seems to show that Murty was the first to give a fully explicit construction.

The girth 5 case has also been studied by Exoo, both alone and in combination with Jajcay, and his constructions supply the remaining bounds.

Geoff Exoo has continued his dominance of the "girth 5 charts" by submitting two more improvements in April 2003.

August 2003

Jason Williford has discovered an extremely beautiful construction for graphs of girth 5, based on a well-known graph that is not regular! Take the points of the desarguesian projective plane PG(2,q), q odd, in its usual representation as the 1d-subspaces of GF(q)^3. Define a graph on the points by declaring two to be adjacent if the corresponding subspaces are orthogonal (with respect to the usual dot product). The resulting graph has no 4-cycles and it was in this context that it was first discovered by Erdos & Renyi. The graph is sometimes called the polarity graph because the points orthogonal to a given point form a line of PG(2,q) and the resulting map from points to lines is a polarity.

There are always q+1 points that lie on their polar line - the absolute points of the polarity - and the remaining points fall into two orbits, being those adjacent to an absolute point and the others. These two orbits induce regular subgraphs, and for q > 7, one of these has girth 5.

When q is congruent to 1 mod 4, the graph on the non-neighbours of the absolute points has binomial(q,2) vertices and is (q+1)/2 regular, and when q is congruent to 3 mod 4, the graph on the neighbours of the absolute points has binomial(q+1,2) vertices and is (q-1)/2 regular.

If we take q = 29, we get a 15-regular graph on 406 vertices.

The girth 6 case

The girth 6 case is mostly covered by projective planes which of course meet the Moore bound whenever k-1 is a prime power. However, what happens when k-1 is NOT a prime power is not known. The first time this occurs is when k=7 and it is known that there is a unique (7,6)-cage, usually named after O'Keefe and Wong. However it was actually first discovered by Baker, as it turns out to be the incidence graph of an elliptic semiplane discovered by Baker. In BCN it is stated that Ito computed the automorphism group as 3 x A(7) which would imply that the semiplane was not self-dual. However there is a subtle error in Ito's argument, and the elliptic semiplane actually is self-dual and the full automorphism group hence has size 6 x 2520 = 15120. It is transitive. (I would like to thank Paul Hafner notifying me of this information; it is also incorporated in the errata for BCN).

The girth 7 case

Little appears to be known about the girth 7 case; it is known that n(k,g) < n(k,g+1) and so the generalized quadrangles of girth 8 provide an upper bound on the size of these graphs, but not much more appears to have been done. (A proof of the monotonicity with respect to girth appears in Holton & Sheehan)

Although the proof of monotonicity does not provide a constructive means of finding a girth 7 graph from a girth 8 graph of the same valency, it seems likely that some generalization of the notion of "excision" for cubic graphs should work. The first hard evidence of this is the (4,7)-graph on 70 vertices, due to due to Brendan McKay and Yang Yuanshen, which was obtained from the generalized quadrangle W(3) in a similar fashion.

The girth 8 case

If there is a generalized quadrangle of order q, then there is a graph of valency q+1 that meets the Moore bound. It is known that there is a generalized quadrangle of order q for all prime powers q. The "classical" GQ of order q is known as W(q). There are many references to this GQ and others; one that is aimed primarily at graph-theorists can be found in the book Algebraic Graph Theory by Godsil & Royle.

The girth 9 case