Cubic graphs with high girth and/or primitive automorphism group
by Jan Kristian Haugland

First of all, despite the fancy title, I am not really presenting anything new here. I have simply made a couple of observations that I would like to share.

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 authors on the subject
(i.e., the smallest cubic graph of a given girth) may have "forgotten" to calculate the girth of these graphs beyond what was done at the time.

I have calculated the girth of each graph in these families with up to one 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:
GirthOrderpGirthOrderpGirthOrderp
61475105343
830372875105
91021710110117567
145062312182131022011
1562031152 03029141 14019
2014 91071184 21837184 96031
2216 20673194 324472032 41273
26143 4501512116 206732159 64071
28527 0462332238 0249725182 104103
291 029 80236724102 07810726573 800151
301 277 66631326187 330131281 000 730229
311 691 29843327290 320191309 363 584383
324 344 31859328656 7001993114 400 678557
337 743 630719301 594 6843373219 195 482613
348 824 250751324 119 2083673492 906 824823
3616 703 420929338 004 14457736148 730 7821213
3745 454 6621297348 487 25846738721 083 4022053
3889 237 47012893531 502 380911Full list
39166 416 75019993632 819 342733
40189 564 11416573739 577 546983
41369 982 29026093863 866 9761153
42418 780 380271939137 553 8201489
Full list40252 434 4561823
41329 845 4861993
42406 632 6342137
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.

The reason why I got interested in sextet graphs in the first place is that it is known (confer [4]) that the only cubic graphs with an automorphism group
that acts primitively on the set of vertices are the sextet graphs S(p) with p ≡ ± 1 (mod 16), in addition to the tetrahedron graph, the Petersen graph,
the Coxeter graph and Wong's graph. What I find curious about these four exceptions is that each one is an induced subgraph of some Kneser graph.
This is known in each case, but I am not sure if it is usually pointed out that it holds for all four. It is a beautiful fact that deserves some attention, I think.

The complete graph Kn is of course isomorphic to the Kneser graph KG(n, 1), and n = 4 gives the tetrahedron graph.
The Petersen graph is isomorphic to KG(5, 2), and the Coxeter graph is isomorphic to an induced subgraph of
KG(7, 3) when we remove a Steiner system S(2, 3, 7) from the set of 3-element subsets of a set of 7 elements.

In the remaining case, we start with a Steiner system S(2, 4, 13). For each 3-element subset of the 13 elements that is not a subset of
any of the blocks, we construct a 6-element set in the following manner. For each pair of elements in the 3-element subset, find the
block in the Steiner system that contains it, and add the other two elements of the block to the new set. This gives an induced subgraph
of KG(13, 6) that is isomorphic to Wong's graph. (This construction appears to be essentially the same as the one given in [5].)

Example: A Steiner system S(2, 4, 13) is given by the blocks (0 1 2 3), (0 4 5 6), (0 7 8 9), (0 10 11 12), (1 4 7 10), (1 5 8 11), (1 6 9 12),
(2 4 8 12), (2 5 9 10), (2 6 7 11), (3 4 9 11), (3 5 7 12), (3 6 8 10). {0, 1, 4} is not a subset of any of the blocks. {0, 1} is a subset of the
block (0 1 2 3), from which we extract 2 and 3. {0, 4} is a subset of the block (0 4 5 6), from which we extract 5 and 6. {1, 4} is a subset
of (1 4 7 10), from which we extract 7 and 10. This gives us the set {2, 3, 5, 6, 7, 10}, corresponding to one vertex in KG(13, 6).

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.)
[4]C.-H. Li, Z. P. Lu and D. Marušič. On primitive permutation groups with small suborbits and their orbital groups, J. Algebra 279 (2004) 749-770.
[5]N. L. Biggs, Algebraic Graph Theory, Cambridge University Press (1974).