Cubic Cages

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.

Table of Contents


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

n(k,g) = 1 + k + k(k-1) + ... + k(k-1)^((g-3)/2)
and if g is even, then
n(k,g) = 1 + k + k(k-1) + ... + k(k-1)^(g/2-2) + (k-1)^(g/2-1)

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.




Cubic cages of small girth

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.

Cubic cages of small girth
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 parameter c(G)

The known lower bounds on the size of a cage of girth g are of the form K (20.5 g).

Therefore if a candidate graph has n vertices, and girth g, and we define the parameter

c(G) = log_2(n)/g
then 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.




Notes

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.




Cubic cages of girth 5

The Petersen graph needs no introduction. Those who disagree may read Holton and Sheehan [HoS 93].




Cubic cages of girth 6

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




Cubic cages of girth 7

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.




Cubic cages of girth 8

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.




Cubic cages of girth 9

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.




Cubic cages of girth 10

These graphs were found by O'Keefe and Wong [OKW 80] .




Cubic cages of girth 11

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




Cubic cages of girth 12

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




Cubic cages of girth 13

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!




Cubic cages of girth 14

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:

  1. (January 2002)

    A new 384 vertex graph found by Exoo has superceded the previously best-known example; this graph has automorphism group of size 96.

  2. (original)

    The previously best graph was a Cayley graph on 406 vertices described by Biggs [Big 89].




Cubic cages of girth 15

The smallest known example is the sextet graph S(31) described by Biggs [Big 89].




Cubic cages of girth 16

  1. Exoo (December 2002)

    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 Z2 x Z3 x Z16.

  2. The smallest known example is described by Biggs [Big 89].




Cubic cages of girth 17

The following list shows successive improvements in the bounds as they come to my attention:

  1. 2176 vertices (Exoo) May 1 2003

    A diameter 13, girth 17 graph with automorphism group of order 544; it has four orbits of length 544.

  2. 2408 vertices (Exoo) Dec 5 2002

    A diameter 13, girth 17 graph with automorphism group of order 602. It has five orbits, 2 of length 301, 3 of length 602.

  3. 2520 vertices (Exoo [Exo 01])

    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:

    252014 (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.

  4. 2978 vertices (Bray, Parker and Rowley [BPR 00])

    Excision on the 3024 vertex graph of girth 18.

  5. 4034 vertices (Biggs/Whitehead)

    Excision on the 4080 vertex graph of girth 18.

  6. 4080 vertices (Conder)

    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.




Cubic cages of girth 18

The following list shows successive improvements in the bounds as they come to my attention:

  1. Exoo (May 2003)

    Another Cayley graph, this time on 2640 vertices.

  2. Bray (January 2003)

    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.

  3. 3024 vertices (Bray, Parker and Rowley [BPR 00])

    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)
    

  4. 4080 vertices (Conder)

    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.

  5. 4218 vertices (Hoare [Hoa 93])

    The hexagon graph H(37).




Cubic cages of girth 19

The following list shows successive improvements in the bounds as they come to my attention:

  1. 4324 vertices (Hoare [Hoa 93] )

    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.




Cubic cages of girth 20

The following list shows successive improvements in the bounds as they come to my attention:

  1. 6048 vertices - Exoo - February 2005

    A 6048-vertex graph with diameter 15 and girth 20; this graph is bipartite and has two equal-size orbits.

  2. 6072 vertices - Parker and Rowley - January 2003

    A 6072-vertex graph with diameter 14 and girth 20; transitive with automorphism group of size 24288.

  3. 8096 vertices (Bray, Parker and Rowley [BPR 00])

    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)
    

  4. 8648 vertices (Whitehead)

    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.

  5. 12180 vertices (Conder)

    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)
    

  6. 14910 vertices (Biggs [Big 89])

    The sextet graph S(71).




Cubic cages of girth 21

The following list shows successive improvements in the bounds as they come to my attention:

  1. (March 2005) 16028 vertices (Exoo)

    Another improvement from Geoff Exoo obtained by a variant of excision.

  2. 16112 vertices (Biggs/Hoare)

    Excision from S(73) - a 16206 vertex graph of girth 22.

  3. 19584 vertices (Conder)

    Cayley graph of GL(2,17) generated by the two 2x2 matrices (0,11,14,0) and (6,15,2,10).

  4. 25308 vertices (Conder)

    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)
    




Cubic cages of girth 22

The following list shows successive improvements in the bounds as they come to my attention:

  1. 16206 vertices (Whitehead)

    The sextet graph S(73).

  2. 24288 vertices (Conder)

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

  3. 32736 vertices (Conder)

    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)
    




Cubic cages of girth 23

The following list shows successive improvements in the bounds as they come to my attention:

  1. 49482 vertices (Bray, Parker and Rowley [BPR 00])

    Excision from the 49608 vertex graph with girth 24.

  2. 59640 vertices (Conder)

    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.

  3. 74412 vertices (Conder)

    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)
    




Cubic cages of girth 24

The following list shows successive improvements in the bounds as they come to my attention:

  1. 49608 vertices (Bray, Parker and Rowley [BPR 00])

    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)
    

  2. 64824 vertices (Conder)

    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.

  3. 79464 vertices (Conder)

    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)
    




Cubic cages of girth 25

The following list shows successive improvements in the bounds as they come to my attention:

  1. 109010 vertices (Bray, Parker and Rowley [BPR 00])

    Excision from the 109200 vertex graph of girth 26.




Cubic cages of girth 26

The following list shows successive improvements in the bounds as they come to my attention:

  1. 109200 vertices (Bray, Parker and Rowley [BPR 00])

    The construction B(G,X) with G = (PSL(2,25) x 7) : 3) : 2.




Cubic cages of girth 27

The following list shows successive improvements in the bounds as they come to my attention:

  1. 285852 vertices (Bray, Parker and Rowley [BPR 00])

    The construction B(G,X) with G = PSL(2,83) x C_3.




Cubic cages of girth 28

The following list shows successive improvements in the bounds as they come to my attention:

  1. 415104 vertices (Bray, Parker and Rowley [BPR 00])

    The construction B(G,X) with G = PGL(2,47) x A_4.




Cubic cages of girth 29

The following list shows successive improvements in the bounds as they come to my attention:

  1. 1143408 vertices (Bray, Parker and Rowley [BPR 00])

    The construction B(G,X) with G = PGL(2,83) x A_4.




Cubic cages of girth 30

The following list shows successive improvements in the bounds as they come to my attention:

  1. 1227666 vertices (Hoare)

    The sextet graph S(313)




Cubic cages of girth 31

The following list shows successive improvements in the bounds as they come to my attention:

  1. 3649794 vertices (Bray, Parker and Rowley [BPR 00])

    Excision from the 3650304 vertex graph of girth 32.




Cubic cages of girth 32

The following list shows successive improvements in the bounds as they come to my attention:

  1. 3650304 vertices (Bray, Parker and Rowley [BPR 00])

    The construction B(G,X) with G = PGL(2,97) x S_4.





References

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.

[Bal73] 48#5916
A.T. Balaban,
Trivalent graphs of girth nine and eleven and relationships among the cages,
Rev. Roumaine Math 18, 1973, 1033-1043.

[BiH 80] 81e:05112
N.L. Biggs and M.J. Hoare,
A trivalent graph with 58 vertices and girth 9,
Discrete Math 30, 1980, 299-301.

[BiH 83] 85a:05038
N.L. Biggs and M.J. Hoare,
The sextet construction for cubic graphs,
Combinatorica 3, 1983, 153-165.

[Big 89] 90k:05083
N.L. Biggs, Cubic Graphs with Large Girth,
Combinatorial Mathematics: Proceedings of the Third International Conference,
Annals of the New York Academy of Sciences 555, 1989, 56-62.

[Big 93] 95h:05105
N.L. Biggs,
Algebraic Graph Theory (2nd ed.),
Cambridge University Press, 1993.

[Big 98] 99j:05097
N.L. Biggs,
Constructions for Cubic Graphs of Large Girth,
Electronic Journal of Combinatorics, 5, 1998.

[BPR 00] 2000j:05055
J. Bray, C. Parker and P. Rowley,
Cayley type graphs and cubic graphs of large girth,
Discrete Math, 214, 2000, 113-121.

[BMS 95] 96i:05138
G. Brinkmann, B. D. McKay and C. Saager,
The smallest cubic graphs of girth nine,
Combinatorics Probability and Computing 5, 1995, 1--13.

[BCN 89] 90e:05001
A.E. Brouwer, A.M Cohen and A. Neumaier.
Distance regular graphs,
Springer-Verlag, 1989.

[Exo 96]
G. Exoo.
A Simple Method for Constructing Small Cubic Graphs of Girths 14, 15 and 16.
Electronic Journal of Combinatorics, 3, 1996.

[Exo 01]
G. Exoo.
A Trivalent Graph of Girth 17,
Australasian Journal of Combinatorics, To appear 2001.

[FeH 64] 30:1189
W. Feit and G. Higman.
The non-existence of certain generalized polygons.
Journal of Algebra 1, 1964, 114 - 131.

[Hoa 93] 94j:05058
M. Hoare.
Triplets and Hexagons,
Graphs and Combinatorics 9, 1993, 225 - 233.

[HoS 93] 94j:05037
D.A. Holton and J. Sheehan,
The Petersen graph,
Australian Mathematical Society Lecture Notes 7,
Cambridge University Press, 1993.

[OKW 80] 81h:05085
M. O'Keefe and P.K. Wong.
A smallest graph of girth 10 and valency 3.
Journal of Combinatorial Theory (B) 29, 1980, 91 - 105.

[Won 82] 83c:05080
P.K. Wong.
Cages - a survey,
Journal of Graph Theory 6, 1982, 1-22.




Home © Gordon Royle, gordon@csse.uwa.edu.au, 1996-2003 (last modified: Jan 2003)