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