A cubic symmetric graph is a symmetric cubic (i.e., regular of order 3). Such graphs were first studied by Foster (1932). They have since been the subject of much interest and study. Since cubic graphs must have an even number of vertices, so must cubic symmetric graphs.
Bouwer et al. (1988) published data for all connected cubic symmetric graphs on up to 512 vertices. Conder and Dobcsányi (2002) found all cubic symmetric graphs up to 768 vertices. Royle maintains a list of known cubic symmetric graphs with fewer than 1000 vertices. (This list is known to be complete for up to 768 vertices, but includes only the Cayley graphs for 770-998 vertices.) All cubic symmetric graphs up to 2048 vertices were subsequently enumerated by M. Condor in August 2006 (Condor).
The numbers of disconnected cubic symmetric graphs on , 4, 6, 8, ... nodes are 0, 0, 0, 1, ..., the smallest of which are illustrated above.
Connected cubic symmetric graphs on 102 or fewer nodes are illustrated above, denoted , where commemorates Foster, is the number of vertices, and a letter , , , etc. is appended to indicate the first, second, etc. such graph on vertices (Royle).
Many connected cubic symmetric graphs, including , and are Cayley graphs. is isomorphic to the generalized Petersen graph and was constructed by Foster (1932), Coxeter (1950), and Frucht (1952). The "apparently new symmetrical graph with 64 vertices and girth 8" discussed by Frucht (1952) is . is the rolling polyhedron graph of the regular icosahedron.
The numbers of connected cubic symmetric graphs on , 4, ... nodes are 0, 1, 1, 1, 1, 0, 1, 1, 1, 2, ... (OEIS A059282). All cubic symmetric graphs having up to 60 nodes are Hamiltonian, with the exception of the Petersen graph (10 nodes) and the Coxeter graph (28 nodes), so the numbers of Hamiltonian connected cubic symmetric graphs are therefore 0, 1, 1, 1, 0, 0, 1, 1, 1, 2, 0, 1, 1, ... (OEIS A091430). The first few orders of connected cubic symmetric graphs are 4, 6, 8, 10, 14, 16, 18, 20, 20, 24, 26, 28, 30, 32, 38, 40, ... (OEIS A075124.
Connected cubic symmetric graphs on 102 or fewer nodes are summarized in the table below. In this table, H stands for Hamiltonian and * indicates a graph having no LCF notation of order .
graph | Hamiltonian | LCF notation | |
4A | tetrahedral graph | yes | |
6A | (utility graph) | yes | |
8A | cubical graph | yes | |
10A | Petersen graph | no | -- |
14A | Heawood graph | yes | |
16A | Moebius-Kantor graph | yes | |
18A | Pappus graph | yes | |
20A | dodecahedral graph | yes | |
20B | Desargues graph | yes | |
24A | Nauru graph | yes | |
26A | yes | ||
28A | Coxeter graph | no | -- |
30A | Tutte 8-cage | yes | |
32A | Dyck graph | yes | |
38A | yes | ||
40A | yes | ||
42A | yes | ||
48A | yes | ||
50A | yes | ||
54A | yes | ||
56A | yes | ||
56B | yes | ||
56C | yes | * | |
60A | yes | ||
62A | yes | ||
64A | yes | ||
72A | yes | ||
74A | yes | ||
78A | yes | ||
80A | yes | ||
84A | yes | * | |
86A | yes | ||
90A | Foster graph | yes | |
96A | yes | ||
96B | yes | ||
98A | yes | ||
98B | yes | ||
102A | Biggs-Smith graph | yes | * |
The plots above show some alternate embeddings for selected cubic symmetric graphs.
Many cubic symmetric graphs (excepting the tetrahedral graph, utility graph, and possibly others) have unit-distance embeddings, as illustrated above in embeddings mainly due to Gerbracht (2008, pers. comm., Dec. 2009-Jan. 2010).