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

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