Overall data

Census of connected cubic vertex-transitive graphs

On this page, we present some overall data extracted from our census of connected cubic vertex-transitive graphs of order at most 1280. For basic definitions, see terminology.

Number of graphs of order at most n

The figure below shows the number of connected cubic vertex-transitive graphs of order at most n (these are the black data points). Superimposed on this data (in gray) is the graph of the function n-->n2/15, which seems to be a close approximantion on the range considered.

C4graph

Number of graphs of order 1280 by type

The next table gives the number of connected cubic vertex-transitive graphs of order at most 1280, discriminating with respect to whether the graphs are Cayley or not and with respect to the number m of orbits of the automorphism group on the arcs (in particular, for m=1, we have the arc-transitive graphs and for m=3, we have the GRRs).

m=1 m=2 m=3 Total
Cayley 386 11853 97687 109926
non-Cayley 96 1338 0 1434
Total 482 13191 97687 111360

The next figure compares the proportion of Cayley graphs (in black), GRRs (with a dashed line) and dihedrants (in gray) to the total number of connected cubic vertex-transitive graphs of order at most n.

C4graph

Hamiltonian cycles

With the exception of the four well-known exceptions (the Petersen and the Coxeter graphs, together with their truncations), all graphs in this census admit an Hamiltonian cycle.

Girth and diameter: extremal examples

Write ncay(g) (respectively nvt(g)) for the smallest order of a cubic Cayley graph (respectively cubic vertex-transitive graph) of girth g. Using our census, we can compute the values of these two functions for g at most 16 and obtain the following table.

g ncay(g) nvt(g)
3 4 4
4 6 6
5 50 10
6 14 14
7 30 26
8 42 30
9 60 60
10 96 80
11 192 192
12 162 162
13 272 272
14 406 406
15 864 620
16 1008 1008

Write mcay(d) (respectively mvt(d)) for the largest order of a cubic Cayley graph (respectively cubic vertex-transitive graph) of diameter d. Using our census, we can compute the values of these two functions for d at most 8 and obtain some lower bounds for d at most 12.

d mcay(g) mvt(g)
2 8 10
3 14 14
4 24 30
5 60 60
6 72 82
7 168 168
8 300 300
9 >=506 >=546
10 >=882 >=1250
11 >=1250 >=1250
12 >=1250 >=1250

Back to the main page.

by Primož Potočnik, Pablo Spiga and Gabriel Verret, February 2012.