This site lists the known cubic cages of small girth. If you can beat any of the records listed below, then please e-mail gordon@csse.uwa.edu.au
Latest News |
---|
February 2005: Geoff Exoo has made further improvement for girth 20 cubic graphs. |
There is a separate page for higher valency cages.
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.
The following table lists the currently known values for the size of a cubic cage. For certain small values of g the cages themselves are all known, and are given here explicitly. For larger values of g a range is given - the lower value is either the trivial bound n(3,g) or a bound that has been laboriously increased by extensive computation, while the upper bound is simply the size of the smallest known cubic graph of that girth, which is given explicitly.
Under the column labelled Number is listed the number of graphs known that meet the upper bound. Numbers not known to be exact are followed by a + symbol (so 1+ means that one example is known, but there may be more).
The graphs are listed in a new format for sparse graphs, called sparse6 which can be transparently read with the same reader as the graph6 format.
The Cages | Smallest Known | n(3,g) | Number | Reference | Notes |
---|---|---|---|---|---|
(3,3)-cages | 4 | 4 | 1 | K_4 | - |
(3,4)-cages | 6 | 6 | 1 | K_3,3 | - |
(3,5)-cages | 10 | 10 | 1 | Petersen | more |
(3,6)-cages | 14 | 14 | 1 | Heawood | more |
(3,7)-cages | 24 | 22 | 1 | McGee graph | more |
(3,8)-cages | 30 | 30 | 1 | Tutte's 8-cage | more |
(3,9)-cages | 58 | 46 | 18 | Brinkmann/McKay/Saager | more |
(3,10)-cages | 70 | 62 | 3 | O'Keefe/Wong | more |
(3,11)-cages | 112 | 94 [112] | 1 | McKay/Myrvold - Balaban | more |
(3,12)-cages | 126 | 126 | 1 | Generalized hexagon | more |
(3,13)-cages | 272 | 190 [202] | 1+ | McKay/Myrvold - Hoare | more |
(3,14)-cages | 384 | 254 [258] | 1+ | McKay - Exoo | more |
(3,15)-cages | 620 | 382 | 1+ | Biggs | more |
(3,16)-cages | 960 | 510 | 1+ | Exoo | more |
(3,17)-cages | 2176 | 766 | 1+ | Exoo | more |
(3,18)-cages | 2640 | 1022 | 1+ | Exoo | more |
(3,19)-cages | 4324 | 1534 | 1+ | H(47) | more |
(3,20)-cages | 6048 | 2046 | 1+ | Exoo | more |
(3,21)-cages | 16028 | 3070 | 1+ | Exoo | more |
(3,22)-cages | 16206 | 4094 | 1+ | Whitehead S(73) | more |
(3,23)-cages | 49482 | 6142 | 1+ | Bray/Parker/Rowley | more |
(3,24)-cages | 49608 | 8190 | 1+ | Bray/Parker/Rowley | more |
(3,25)-cages | 109010 | 12286 | 1+ | Bray/Parker/Rowley | more |
(3,26)-cages | 109200 | 16382 | 1+ | Bray/Parker/Rowley | more |
(3,27)-cages | 285852 | 24574 | 1+ | Bray/Parker/Rowley | more |
(3,28)-cages | 415104 | 32766 | 1+ | Bray/Parker/Rowley | more |
(3,29)-cages | 1143408 | 49150 | 1+ | Bray/Parker/Rowley | more |
(3,30)-cages | 1227666 | 65534 | 1+ | Hoare S(313) | more |
(3,31)-cages | 3649794 | 98302 | 1+ | Bray/Parker/Rowley | more |
(3,32)-cages | 3650304 | 131070 | 1+ | Bray/Parker/Rowley | more |
The known lower bounds on the size of a cage of girth g are of the form K (2^{0.5 g}).
Therefore if a candidate graph has n vertices, and girth g, and we define the parameter
c(G) = log_2(n)/gthen how close this value is to 0.5 is a (rough) measure of how close the graph is to optimal.
The following diagram shows the values of c(G) for the graphs given in the table above.
Several surveys on cages, each from a slightly different viewpoint have been published. Amongst these are Chapter 23 of Biggs [Big 93] , Chapter 6 of Holton and Sheehan [HoS 93] , Section 6.9 of Brouwer, Cohen and Neumaier [BCN 89] and the paper by Wong [Won 82]. Biggs [Big 98] has recently published a new survey.
A graph meeting the naive bound is a Moore graph if g is odd and a generalized polygon if g is even. The only cubic Moore graph is the Petersen graph, and the only cubic generalized polygons are the generalized 2-gon K3,3, the generalized triangle PG(2,2), the generalized quadrangle W(2) and the generalized hexagon GH(2,2). There are no regular generalized octagons, and by Feit and Higman [FeH 64] no other possibilities.
It has frequently been observed that Cayley graphs seem to provide examples of cages, but there appear to have been few attempts at systematic searches, and the Cayley graphs are usually presented with no particular mention of how they were found. One advantage of working with Cayley graphs is that the girth can be found by examining a small percentage of the graph (usually just by expanding around a vertex until a cycle is found). Both Dan Ashlock and Marston Conder have independently developed software for this task (in Grape and Magma respectively), and it is likely that some new bounds will be broken shortly.
I have constructed all the cubic Cayley graphs on up to 1000 vertices, excluding those on 512 and 768 vertices, but without success in finding any improvements in the bounds.
[April 1998] I just received an interesting new paper from John Bray, Christopher Parker and Peter Rowley. Consider a group G with a generating set X = (a,b) where |a| = 2 and |b| = 3. Form the Cayley graph C(G,X) - hopeless for cages you say, because it obviously contains stacks of triangles. However BPR have noted that if there are no cycles of length 4 (surely such graphs never have cycles of length 4?) you can shrink all the triangles to single vertices in the obvious way, and get a cubic graph of 1/3rd the size. They call this construction B(G,X). By luck or by judgement, this process may yield a cage if the initial graph is appropriately chosen. For example, the Heawood graph - the unique (3,6) cage - arises from this construction from a Cayley graph of order 42. More importantly however, this construction allows you to escape from the class of Cayley graphs - although the graph is transitive it may well not be Cayley. The first time this happens is a Cayley graph of order 60 which reduces to a non-Cayley graph on 20 vertices (an antipodal double cover of the ubiquitous Petersen graph). By checking it on my lists of cubic Cayley graphs on up to 1000 vertices, I can confirm it gives nothing new in that range.
The Petersen graph needs no introduction. Those who disagree may read Holton and Sheehan [HoS 93].
A graph meeting the naive bound for even girth is a generalized polygon. In this case the cage is the point/line incidence graph of the projective plane of order 2 (the Fano plane).
A unique cage, with automorphism group of size 32. The graph is not vertex-transitive having orbits of length 8 and 16. Graph was found by McGee and then proven unique by Tutte.
A graph meeting the naive bound for even girth is a generalized polygon. In this case the cage is the point/line incidence graph of the generalized quadrangle W(2). The graph is known also as Tutte's 8-cage as it was first described by Tutte. The graph is symmetric, in fact it is a 5-arc transitive cubic graph.
The first (3,9)-cage was found by Biggs and Hoare [BiH 80] . Brendan McKay proved by computation that 58 vertices was indeed the size of a cage, and then with Brinkmann and Saager [BMS 95] completed an exhaustive search yielding all 18 (3,9)-cages.
These graphs were found by O'Keefe and Wong [OKW 80] .
Computations by Brendan McKay and Wendy Myrvold have demonstrated that a cage must have exactly 112 vertices. The fact that an 11-cage had size 112 was known some time earlier, but in March 2003 it was announced that there is a unique such graph. This example was found by Balaban [Bal 73].
A graph meeting the naive bound for even girth is a generalized polygon. In this case the cage is the point/line incidence graph of the generalized hexagon of order 2. This generalized hexagon is not self-dual so the automorphism group of the graph has two orbits (being the points and lines of the GH).
Computations by McKay and Myrvold have lifted the lower bound from the naive value of 190 to at least 202 (the computation to prove that there were none on 200 vertices took 2.3 years of cpu time). The smallest graph known is a Cayley graph on 272 vertices, found by Miles Hoare (now Miles Whitehead), and described in the paper by Biggs [Big 89]. Marston Conder also independently found it many years later!
Computations by McKay and Myrvold have raised the lower bound from the naive Moore bound to 258.
The following list shows successive improvements in the upper bounds as they come to my attention:
A new 384 vertex graph found by Exoo has superceded the previously best-known example; this graph has automorphism group of size 96.
The previously best graph was a Cayley graph on 406 vertices described by Biggs [Big 89].
The smallest known example is the sextet graph S(31) described by Biggs [Big 89].
Another new record-holder found by Geoff Exoo; the graph has diameter 11 and an automorphism group of size 96, with 10 orbits. The automorphism group is abelian, isomorphic to Z_{2} x Z_{3} x Z_{16}.
The smallest known example is described by Biggs [Big 89].
The following list shows successive improvements in the bounds as they come to my attention:
A diameter 13, girth 17 graph with automorphism group of order 544; it has four orbits of length 544.
A diameter 13, girth 17 graph with automorphism group of order 602. It has five orbits, 2 of length 301, 3 of length 602.
Geoff Exoo has returned to the fray with a simple, yet effective idea. Assume that the graph has a hamilton cycle, and then just specify the remaining 1-factor in a simple way. It is most easily described by example:
2520_{14} (61, 76, 1283, 495, 2206, -61, 1852, -76, -495, 382, -1852, -1283, -2206, -382)
This notation indicates that the graph has 2520 vertices, and that verex 0 is joined to 0+61, vertex 1 to 1+76, etc. When you run out of parameters, simply start from the beginning again. Thus, vertex 14 is also joined to 14+61, vertex 15 to 15+76 etc.
This graph has an automorphism group of order 180 (which is 2520/14), and has diameter 13.
Excision on the 3024 vertex graph of girth 18.
Excision on the 4080 vertex graph of girth 18.
Cayley graph with the following generating involutions:
a = (1, 9)(2, 8)(3, 7)(4, 6)(10, 17)(11, 16)(12, 15)(13, 14) b = (1, 14)(2, 16)(3, 6)(4, 8)(5, 12)(7, 9)(10, 17)(13, 15) c = (1, 12)(2, 13)(3, 17)(4, 5)(6, 16)(8, 15)(9, 10)(11, 14)This graph has an automorphism group of size 8160.
The following list shows successive improvements in the bounds as they come to my attention:
Another Cayley graph, this time on 2640 vertices.
A 2688-vertex graph formed by taking the Cayley graph with the following generators:
(1,8)(2,5)(3,4)(6,10)(7,21)(9,23)(11,22)(12,24)(13,16)(14,15)(17,19)(18,20) (25,32)(26,29)(27,30)(28,31)(34,36) (1,4,13)(2,15,6)(3,10,21)(5,8,22)(7,12,27)(9,25,11)(14,20,31)(16,17,29)(33,35,34)which forms an 8064-vertex graph with triangles. Collapsing the triangles to a vertex yields a 2688-vertex graph with diameter 14 and girth 18.
Cayley graph of PSL(2,8) x C_6 with following generators:
a = (1, 8)(2, 3)(5, 6)(7, 9)(10, 13)(11, 14)(12, 15) b = (1, 6, 9, 5, 7, 2, 3, 4, 8)(10, 15, 14, 13, 12, 11)
Cayley graph with the following generators:
a = (1, 9)(2, 8)(3, 7)(4, 6)(10, 17)(11, 16)(12, 15)(13, 14) b = (1, 11)(2, 5)(3, 8)(4, 14)(6, 15)(7, 12)(9, 17)(10, 13) c = (1, 2)(3, 13)(5, 12)(6, 7)(8, 11)(9, 15)(10, 16)(14, 17)This graph has an automorphism group of size 24480, and hence is a symmetric (in fact 2-arc-transitive) graph.
The hexagon graph H(37).
The following list shows successive improvements in the bounds as they come to my attention:
The hexagon graph H(47). The graph listed is in fact an antipodal "halving" of the 8324 vertex girth 20 graph described below. It is almost certainly H(47) but this is not 100% confirmed.
The following list shows successive improvements in the bounds as they come to my attention:
A 6048-vertex graph with diameter 15 and girth 20; this graph is bipartite and has two equal-size orbits.
A 6072-vertex graph with diameter 14 and girth 20; transitive with automorphism group of size 24288.
The construction B(G,X) with G = 2.PSL(2,23) : 2 and X given by
a = (1, 27)(2, 13)(4, 47)(5, 28)(6, 24)(7, 38)(8, 11)(10, 20)(12, 41)(14, 31) (15, 33)(16, 23)(17, 36) (18, 40)(19, 22)(21, 44)(25, 35)(26, 37)(29, 45) (30, 39)(32, 48)(34, 46)(42, 43) b = (1, 8, 14)(2, 9, 30)(3, 35, 44)(4, 29, 32)(5, 39, 28)(6, 22, 7)(10, 20, 25) (11, 34, 21)(12, 15, 17) (13, 36, 47)(16, 40, 31)(18, 33, 43)(19, 24, 45) (23, 26, 27) (37, 41, 42)(38, 48, 46)
Two graphs of diameter 19 and girth 20 on 8648 vertices; both of them are 3-arc transitive graphs. One is an antipodal double covering of a cubic graph of girth 19 on 4324 vertices (almost certainly H(47)). This 4324 vertex graph is not bipartite and hence can be "doubled" in a way that converts every odd cycle to one of twice the length.
Cayley graph with the following generating involutions:
a = (1, 7)(2, 17)(3, 27)(4, 25)(5, 13)(6, 20)(8, 26)(9, 30)(10, 15)(12, 16) (14, 28)(18, 22)(19, 24)(21, 29) b = (1, 5)(2, 24)(3, 17)(4, 29)(6, 21)(7, 11)(8, 13)(9, 25)(10, 18)(14, 23) (15, 27)(16, 22)(19, 28)(20, 26) c = (1, 16)(2, 13)(4, 22)(5, 7)(6, 14)(8, 15)(9, 23)(10, 28)(11, 20)(12, 21) (17, 24)(18, 26)(19, 30)(25, 27)
The sextet graph S(71).
The following list shows successive improvements in the bounds as they come to my attention:
Another improvement from Geoff Exoo obtained by a variant of excision.
Excision from S(73) - a 16206 vertex graph of girth 22.
Cayley graph of GL(2,17) generated by the two 2x2 matrices (0,11,14,0) and (6,15,2,10).
Cayley graph generated by:
(1, 36)(2, 4)(3, 37)(5, 10)(6, 29)(8, 34)(9, 14)(11, 23)(13, 28)(15, 17)(16, 20)(18, 21)(19, 30)(22, 32)(24, 31)(25, 35)(26, 33)(27, 38) (1, 38)(2, 11)(3, 7)(4, 28)(5, 30)(6, 37)(8, 13)(9, 25)(10, 15)(12, 21)(14, 36)(16, 20)(17, 24)(18, 31)(19, 33)(22, 23)(26, 29)(32, 35) (1, 27)(2, 34)(3, 32)(4, 38)(5, 8)(6, 9)(7, 26)(10, 14)(11, 20)(12, 18)(13, 25)(15, 37)(16, 33)(17, 28)(19, 36)(21, 29)(23, 31)(24, 35)
The following list shows successive improvements in the bounds as they come to my attention:
The sextet graph S(73).
Cayley graph of a subgroup of GL(2,23) generated by the three 2x2 matrices (14,15,10,9), (11,13,12,12) and (20,22,8,3).
Cayley graph with the following generating involutions:
(1, 19)(2, 18)(3, 17)(4, 16)(5, 15)(6, 14)(7, 13)(8, 12)(9, 11)(20, 33)(21, 32)(22, 31)(23, 30)(24, 29)(25, 28)(26, 27) (1, 33)(2, 21)(3, 27)(4, 6)(5, 15)(8, 10)(9, 32)(11, 20)(12, 26)(13, 14)(16, 23)(17, 28)(18, 22)(19, 30)(24, 31)(25, 29) (1, 23)(2, 6)(3, 7)(4, 14)(5, 28)(8, 19)(9, 22)(10, 16)(11, 18)(12, 27)(13, 25)(15, 30)(17, 29)(20, 33)(24, 31)(26, 32)
The following list shows successive improvements in the bounds as they come to my attention:
Excision from the 49608 vertex graph with girth 24.
A 3-arc transitive graph defined as follows: Inside PSL(2,71) take
h = (1, 15, 34)(2, 38, 9)(3, 63, 26)(4, 13, 20)(5, 21, 29)(6, 8, 33)(7, 43, 36) (10, 47, 67)(11, 30, 44)(12, 37, 39)(14, 65, 23)(16, 24, 40)(17, 59, 60) (18, 46, 49)(19, 54, 42)(22, 52, 31)(25, 32, 41)(27, 68, 71)(28, 57, 58) (35, 50, 70)(45, 69, 64)(48, 72, 53)(51, 56, 55)(61, 66, 62) a = (1, 5)(2, 69)(3, 18)(4, 62)(6, 49)(7, 10)(8, 53)(9, 22)(11, 58)(12, 64) (13, 39)(14, 42)(15, 28)(16, 38)(17, 57)(19, 34)(20, 52)(21, 71)(23, 67) (24, 70)(25, 45)(26, 51)(27, 30)(29, 56)(31, 60)(32, 36)(33, 47)(35, 40) (37, 46)(41, 59)(43, 54)(44, 61)(48, 65)(50, 68)(55, 66)(63, 72),and let G be the coset graph with generating set { a, h^-1*a*h, h*a*h^-1 } modulo the subgroup generated by h.
Cayley graph with the following generating involutions:
(1, 20)(2, 36)(3, 39)(4, 51)(5, 35)(6, 54)(7, 18)(8, 44)(9, 34)(10, 25)(11, 45)(12, 42)(13, 38)(14, 19)(15, 17)(16, 48)(21, 24)(22, 37)(23, 26)(27, 46)(28, 33)(29, 40)(30, 32)(31, 53)(41, 47)(43, 50) (1, 42)(2, 38)(3, 29)(4, 54)(5, 30)(6, 46)(7, 47)(8, 25)(9, 12)(10, 31)(11, 52)(13, 33)(14, 37)(15, 51)(16, 39)(17, 19)(18, 27)(20, 40)(22, 43)(23, 48)(24, 50)(26, 35)(28, 45)(34, 36)(41, 44)(49, 53) (1, 6)(2, 36)(3, 54)(4, 9)(5, 32)(7, 10)(8, 28)(11, 51)(12, 19)(13, 53)(14, 50)(15, 43)(16, 39)(18, 30)(20, 33)(21, 49)(22, 38)(23, 24)(25, 48)(26, 42)(27, 29)(31, 44)(34, 46)(35, 37)(40, 41)(45, 52)
The following list shows successive improvements in the bounds as they come to my attention:
The construction B(G,X) with G = PSL(2,53) x C2 and X given by
a = (1, 4)(2, 5)(3, 6)(7, 23)(8, 16)(9, 14)(10, 24)(11, 46)(12, 21)(15, 32) (17, 47)(18, 41)(19, 49)(20, 55)(22, 29)(25, 48)(26, 36)(27, 38)(28, 39) (30, 40)(31, 35)(33, 60)(34, 51)(37, 44)(42, 56)(43, 59)(45, 54)(50, 58) (52, 57) b = (7, 49, 12)(8, 52, 57)(9, 35, 44)(10, 34, 18)(11, 53, 48)(13, 56, 55) (14, 17, 21)(15, 31, 38)(16, 25, 51)(19, 60, 40)(20, 54, 41)(22, 29, 45) (23, 24, 32)(26, 50, 42)(27, 33, 30)(28, 36, 37)(39, 43, 46)(47, 59, 58)
A 3-arc transitive graph constructed as follows: Inside PSL(2,73) take
h = (1, 8, 14)(2, 25, 72)(4, 21, 35)(5, 36, 47)(6, 69, 43)(7, 46, 32) (9, 45, 37)(10, 66, 27)(11, 23, 52)(12, 65, 17)(13, 42, 54)(15, 16, 34) (18, 29, 60)(19, 58, 33)(20, 56, 28)(22, 70, 59)(24, 68, 39)(26, 71, 41) (30, 44, 61)(31, 49, 50)(38, 73, 55)(40, 63, 67)(48, 74, 53)(51, 57, 64) a = (1, 70)(2, 73)(3, 19)(4, 8)(5, 67)(6, 40)(7, 21)(9, 55)(10, 45)(11, 33) (12, 58)(13, 28)(14, 20)(15, 25)(16, 35)(17, 37)(18, 31)(22, 57)(23, 72) (24, 41)(26, 43)(27, 61)(30, 50)(32, 51)(34, 56)(36, 49)(39, 54)(42, 52) (44, 69)(46, 60)(47, 53)(48, 64)(59, 63)(62, 74)(65, 68)(66, 71).and let G be the coset graph with generating set {a, h^-1*a*h, h*a*h^-1} modulo the subgroup generated by h.
Cayley graph with the following generating involutions:
a = (1, 36)(2, 32)(3, 42)(4, 31)(5, 9)(6, 43)(7, 35)(8, 12)(10, 26)(11, 18) (13, 30)(14, 19)(15, 29)(16, 25)(17, 37)(20, 39)(21, 34)(22, 41)(23, 38) (24, 44)(27, 40) b = (1, 34)(2, 6)(3, 19)(4, 22)(5, 10)(7, 21)(8, 35)(9, 14)(11, 28)(12, 42) (13, 17)(15, 41)(16, 44)(18, 29)(20, 30)(23, 38)(24, 31)(25, 40)(26, 27) (32,39)(33, 43)(36, 37) c = (1, 29)(2, 28)(3, 27)(4, 26)(5, 25)(6, 24)(7, 23)(8, 22)(9, 21)(10, 20) (11, 19)(12, 18)(13, 17)(14, 16)(30, 44)(31, 43)(32, 42)(33, 41)(34, 40) (35, 39)(36, 38)
The following list shows successive improvements in the bounds as they come to my attention:
Excision from the 109200 vertex graph of girth 26.
The following list shows successive improvements in the bounds as they come to my attention:
The construction B(G,X) with G = (PSL(2,25) x 7) : 3) : 2.
The following list shows successive improvements in the bounds as they come to my attention:
The construction B(G,X) with G = PSL(2,83) x C_3.
The following list shows successive improvements in the bounds as they come to my attention:
The construction B(G,X) with G = PGL(2,47) x A_4.
The following list shows successive improvements in the bounds as they come to my attention:
The construction B(G,X) with G = PGL(2,83) x A_4.
The following list shows successive improvements in the bounds as they come to my attention:
The sextet graph S(313)
The following list shows successive improvements in the bounds as they come to my attention:
Excision from the 3650304 vertex graph of girth 32.
The following list shows successive improvements in the bounds as they come to my attention:
The construction B(G,X) with G = PGL(2,97) x S_4.
Each reference is accompanied by a direct link to its review in Math Reviews (if it has one). These will not work unless your institution has a subscription to online Math Reviews.