Cubic Symmetric Graph

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