The connected 3-regular (cubic) simple graphs are listed for small vertex numbers.
Connectivity The number of connected simple cubic graphs on 4, 6, 8, 10, ... vertices is 1, 2, 5, 19, ... . A classification according to edge connectivity is made as follows: the 1-connected and 2-connected graphs are defined as usual. This leaves the other graphs in the 3-connected class because each 3-regular graph can be split by cutting all edges adjacent to any of the vertices. To refine this definition in the light of the algebra of coupling of angular momenta (see below), a subdivision of the 3-connected graphs is helpful. We shall call Non-trivially 3-connected those that can be split by 3 edge cuts into sub-graphs with at least two vertices remaining in each part Cyclically 4-connected—all those not 1-connected, not 2-connected, and not non-trivially 3-connected This declares the numbers 3 and 4 in the fourth column of the tables below.
Pictures Ball-and-stick models of the graphs in another column of the table show the vertices and edges in the style of images of molecular bonds. Comments on the individual pictures contain girth, diameter, Wiener index, Estrada index and Kirchhoff index. Aut is the order of the Automorphism group of the graph. A Hamiltonian circuit (where present) is indicated by enumerating vertices along that path from 1 upwards. (The positions of the vertices have been defined by minimizing a pair potential defined by the squared difference of the Euclidean and graph theoretic distance, placed in a Molfile, then rendered by Jmol.)
LCF notation The LCF notation is a notation by Joshua Lederberg, Coxeter and Frucht, for the representation of cubic graphs that are Hamiltonian.
The two edges along the cycle adjacent to any of the vertices are not written down.
Let be the vertices of the graph and describe the Hamiltonian circle along the vertices by the edge sequence . Halting at a vertex , there is one unique vertex at a distance joined by a chord with ,
The vector of the integers is a suitable, although not unique, representation of the cubic Hamiltonian graph. This is augmented by two additional rules: If a , replace it by ; avoid repetition of a sequence of if these are periodic and replace them by an exponential notation. Since the starting vertex of the path is of no importance, the numbers in the representation may be cyclically permuted. If a graph contains different Hamiltonian circuits, one may select one of these to accommodate the notation. The same graph may have different LCF notations, depending on precisely how the vertices are arranged.
Often the anti-palindromic representations with
are preferred (if they exist), and the redundant part is then replaced by a semicolon and a dash "; –". The LCF notation , for example, and would at that stage be condensed to .
Table 4 vertices
diam. girth Aut. connect. LCF names picture1 3 24 4 4 K4
6 vertices diam.girthAut.connect. LCF names picture23123 [2, 3, −2]2 prism graph Y3 24724 6 K3, 3, utility graph
8 vertices diam.girthAut.connect. LCF names pictures3316 2 [2, 2, −2, −2]2 3343 [4, −2, 4, 2]2 or [2, 3, −2, 3; –] 23123 [2, 4, −2, 3, 3, 4, −3, −3] 34484 [−3, 3]4 cube graph 24164 8 or [4, −3, 3, 4]2 Wagner graph
10 vertices diam.girthAut.connect. LCF names pictures53321 Edge list 0–1, 0–6, 0–9, 1–2, 1–5, 2–3, 2–4, 3–4, 3–5, 4–5, 6–7, 6–8, 7–8, 7–9, 8–9 4342 [4, 2, 3, −2, −4, −3, 2, 2, −2, −2] 3382 [2, −3, −2, 2, 2; –] 33162 [−2, −2, 3, 3, 3; –] 43162 [2, 2, −2, −2, 5]2 3323 [2, 3, −2, 5, −3]2 [3, −2, 4, −3, 4, 2, −4, −2, −4, 2] 33123 [2, −4, −2, 5, 2, 4, −2, 4, 5, −4] 3323 [5, 3, 5, −4, −3, 5, 2, 5, −2, 4] [−4, 2, 5, −2, 4, 4, 4, 5, −4, −4] [−3, 2, 4, −2, 4, 4, −4, 3, −4, −4] 3343 [−4, 3, 3, 5, −3, −3, 4, 2, 5, −2] [3, −4, −3, −3, 2, 3, −2, 4, −3, 3] 3363 [3, −3, 5, −3, 2, 4, −2, 5, 3, −4] 3343 [2, 3, −2, 3, −3; –] [−4, 4, 2, 5, −2]2 3363 [5, −2, 2, 4, −2, 5, 2, −4, −2, 2] 3383 [2, 5, −2, 5, 5]2 [2, 4, −2, 3, 4; –] 34483 [5, −3, −3, 3, 3]2 3484 [5, −4, 4, −4, 4]2 [5, −4, −3, 3, 4, 5, −3, 4, −4, 3] 3444 [5, −4, 4, 5, 5]2 [−3, 4, −3, 3, 4; –] [4, −3, 4, 4, −4; –] [−4, 3, 5, 5, −3, 4, 4, 5, 5, −4] 34204 10 [−3, 3]5 [5, 5, −3, 5, 3]2 34204 [−4, 4, −3, 5, 3]2 Pentagonal prism, G5, 2 251204 Petersen graph
12 vertices