Cubic symmetric graphs (The Foster Census)

This site lists the known cubic symmetric graphs with less than 1000 vertices. It is known to be complete for up to 768 vertices, but for 770-998 vertices it includes only the Cayley graphs.

If anyone has any further cubic symmetric graphs to be added, then please send them to me. I hope to implement an automated new graph submission system shortly.

This data was collated by Gordon Royle , Marston Conder , Brendan McKay and Peter Dobscanyi.

Table of Contents


Introduction

A graph is called symmetric if its automorphism group acts transitively on the set of arcs (directed edges) of the graph.

If the graph is cubic, then by Tutte's theorem the automorphism group actually acts regularly on s-arcs for some value of s between 1 and 5, and we say that a graph is s-arc transitive if the group acts regularly on s-arcs, but not transitively on (s+1)-arcs.


The Foster census

Ronald M. Foster started collecting specimens of small cubic symmetric graphs prior to 1934, maintaining a census of all such graphs. In 1988 the then current version of the census was published by I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star in a book entitled The Foster Census (Charles Babbage Research Centre, 1988). and contained data for the graphs on up to 512 vertices.

This book listed constructions of most of the graphs and various data regarding the graphs, but did not explicitly list the graphs themselves.

The main purpose of this archive is to give the explicit listings of graphs, in the hope that this will be of some use to researchers.

In order to maximise the usefulness of this data we have adopted a naming scheme consistent with that used in The Foster Census. So for example, the graph F240B is the graph 240B of The Foster Census, and the graph F126A is the graph 126 of The Foster Census.

The original Foster Census was remarkably complete, in that it missed only a few graphs on under 512 vertices. These graphs are F480B, F432E, F448C, F480C, F480D, F486D, F512D, F512E, F512F, F512G.




The Graphs

There are various ways in which to access the data. The simplest way for those intending further computer processing is simply to download the entire collection of graphs in sparse6 format.

  1. Download The Foster Census (up to 512 vertices)
  2. Download Extended Foster Census (up to 998 vertices)
  3. Download GAP format - a gzipped tar file containing the adjacency matrix in GAP format for each graph (in a separate file).

Alternatively, the graphs can also be viewed in a more human-readable format which I am tentatively calling "cub" format. This is simply a listing of the number of vertices n followed by the 3 neighbours of each of the vertices 0 to n-1 in order, and clearly is only applicable for cubic graphs.

For example, the Petersen graph is given as

10
1 2 3
0 4 5
0 6 7
0 8 9
1 6 8
1 7 9
2 4 9
2 5 8
3 4 7
3 5 6

  1. Download The Foster Census (up to 512 vertices)
  2. Download Extended Foster Census (up to 998 vertices)




Associated Data

In addition to the raw graphs, it is possible to browse through some of the parameters associated with each of the graphs. These listings contain some of the more easily computable paramters such as the diameter and the girth, together with the invariant called the vertex code in The Foster Census.

This data has been prepared in a tabular format for easy browsing.




Hamilton cycles

There are currently only five known vertex-transitive graphs that do not have a hamilton cycle - they are the complete graph on two vertices, the Petersen graph F010A , the Coxeter graph F028A and two graphs derived from the Petersen and Coxeter graphs by replacing each vertex with a triangle.

It is conjectured that all other vertex-transitive graphs are hamiltonian. A slightly weaker conjecture is that all Cayley graphs are hamiltonian.

All the graphs in this collection have been checked for hamilton cycles with only the Petersen and Coxeter graphs having no hamilton cycle.




Distance-regular graphs

All cubic distance-regular graphs are known ( Distance-regular graphs , Brouwer, Cohen and Neumaier, page 221). All but one of the graphs is symmetric on fewer than 512 vertices, hence appears in this catalogue.

Graph Name Vertices Intersection Array
F004A K4 4 {3;1}
F006A K3,3 6 {3,2;1,3}
F008A The cube 8 {3,2,1;1,2,3}
F010A The Petersen graph 10 {3,2;1,1}
F014A The Heawood graph 14 {3,2,2;1,1,3}
F018A The Pappus graph 18 {3,2,2,1;1,1,2,3}
F020A The dodecahedron 20 {3,2,1,1,1;1,1,1,2,3}
F020B The Desargues graph 20 {3,2,2,1,1;1,1,2,2,3}
F028A The Coxeter graph 28 {3,2,2,1;1,1,1,2}
F030A Tutte's 8-cage 30 {3,2,2,2;1,1,1,3}
F090A The Foster graph 90 {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}
F102A The Biggs-Smith graph 102 {3,2,2,2,1,1,1;1,1,1,1,1,1,3}
- Tutte's 12-cage 126 {3,2,2,2,2,2;1,1,1,1,1,3}



Copyright

You may personally use this data for any academic purpose, provided an appropriate reference is given to this site. Permission should be obtained if you wish to incorporate this data into any commercial product or data-set.

Last updated: February 2001