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 programs are 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 | |||||||||||

39 | 166 416 750 | 1999 | 36 | 32 819 342 | 733 | |||||||||||

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

40 | 252 434 456 | 1823 | ||||||||||||||

41 | 329 845 486 | 1993 | ||||||||||||||

42 | 406 632 634 | 2137 |

The sextet graphs

The bipartite double cover of

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

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

The Petersen graph is isomorphic to

In the remaining case, we start with a Steiner system

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

Example: A Steiner system

(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

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