Cubic graphs of high girth
by Jan Kristian Haugland

For some integers n, the smallest known cubic graph of girth n belongs to the family of sextet graphs, described in [1],
or the related hexagon graphs, described in [2]. The latter paper also describes another related family - the triplet graphs.
It would appear, however, that later authors may have forgotten to calculate the girth of these graphs beyond what was done at the time.

I have calculated the girth of the sextet graphs and hexagon graphs with up to one billion vertices, and of the triplet graphs
with up to five billion vertices. Here are the lists of progressively higher girth values. (It is assumed that Hoare's
conjecture on the size of the hexagon graphs H(p) given in [2] is true - and that my program is working correctly!)

 Sextet graphs: Hexagon graphs: Triplet graphs: Girth Order p Girth Order p Girth Order p 6 14 7 5 10 5 3 4 3 8 30 3 7 28 7 5 10 5 9 102 17 10 110 11 7 56 7 14 506 23 12 182 13 10 220 11 15 620 31 15 2 030 29 14 1 140 19 20 14 910 71 18 4 218 37 18 4 960 31 22 16 206 73 19 4 324 47 20 32 412 73 26 143 450 151 21 16 206 73 21 59 640 71 28 527 046 233 22 38 024 97 25 182 104 103 29 1 029 802 367 24 102 078 107 26 573 800 151 30 1 277 666 313 26 187 330 131 28 1 000 730 229 31 1 691 298 433 27 290 320 191 30 9 363 584 383 32 4 344 318 593 28 656 700 199 31 14 400 678 557 33 7 743 630 719 30 1 594 684 337 32 19 195 482 613 34 8 824 250 751 32 4 119 208 367 34 92 906 824 823 36 16 703 420 929 33 8 004 144 577 36 148 730 782 1213 37 45 454 662 1297 34 8 487 258 467 38 721 083 402 2053 38 89 237 470 1289 35 31 502 380 911 40 2 343 516 240 3041 39 166 416 750 1999 36 32 819 342 733 Full list 40 189 564 114 1657 37 39 577 546 983 41 369 982 290 2609 38 63 866 976 1153 42 418 780 380 2719 39 137 553 820 1489 Full list 40 252 434 456 1823 41 329 845 486 1993 42 406 632 634 2137 Full list

The sextet graphs S(367) and S(433) of girth 29 and 31 have fewer vertices than the graphs of corresponding girth in [3].
The bipartite double cover of S(433) of girth 32 has 3,382,596 vertices, which would also be a record.

References:

 [1] N. L. Biggs and M. J. Hoare. The sextet construction for cubic graphs, Combinatorica 3 (1983) 153-165. [2] M. J. Hoare. Triplets and hexagons, Graphs Combin. 9 (1993) 225-233. [3] J. Bray, C. Parker and P. Rowley. Cayley type graphs and cubic graphs of large girth, Discrete Math. 214 (2000) 113-121.(The same table appears here, here and here.)