Table of simple cubic graphs

Last updated December 16, 2024

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, ... (sequence A002851 in the OEIS ). 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 $v$ be the vertices of the graph and describe the Hamiltonian circle along the $p$ vertices by the edge sequence $v 0 v 1, v 1 v 2, ...,v p-2 v p-1, v p-1 v 0$ . Halting at a vertex $v i$ , there is one unique vertex $v j$ at a distance $d i$ joined by a chord with $v i$ ,

j=i+d_{i}\quad ({\bmod {\,}}p),\quad 2\leq d_{i}\leq p-2.

The vector $[d 0, d 1, ..., d p-1]$ of the $p$ integers is a suitable, although not unique, representation of the cubic Hamiltonian graph. This is augmented by two additional rules:

If a $d i > p/2$ , replace it by $d i - p$ ;
avoid repetition of a sequence of $d i$ 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

d_{p-1-i}=-d_{i}\quad ({\bmod {\,}}p),\quad i=0,1,\ldots p/2-1

are preferred (if they exist), and the redundant part is then replaced by a semicolon and a dash "; –". The LCF notation $[5, -9, 7, -7, 9, -5] 4$ , for example, and would at that stage be condensed to $[5, -9, 7; -] 4$ .

Table

4 vertices

diam.	girth	Aut.	connect.	LCF	names	picture
1	3	24	4	[2]⁴	K₄

6 vertices

diam.	girth	Aut.	connect.	LCF	names	picture
2	3	12	3	[2, 3, −2]²	prism graph Y₃
2	4	72	4	[3]⁶	K_{3, 3}, utility graph

8 vertices

diam.	girth	Aut.	connect.	LCF	names	pictures
3	3	16	2	[2, 2, −2, −2]²
3	3	4	3	[4, −2, 4, 2]² or [2, 3, −2, 3; –]
2	3	12	3	[2, 4, −2, 3, 3, 4, −3, −3]
3	4	48	4	[−3, 3]⁴	cubical graph
2	4	16	4	[4]⁸ or [4, −3, 3, 4]²	Wagner graph

10 vertices

diam.	girth	Aut.	connect.	LCF	names	pictures
5	3	32	1		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
4	3	4	2	[4, 2, 3, −2, −4, −3, 2, 2, −2, −2]
3	3	8	2	[2, −3, −2, 2, 2; –]
3	3	16	2	[−2, −2, 3, 3, 3; –]
4	3	16	2	[2, 2, −2, −2, 5]²
3	3	2	3	[2, 3, −2, 5, −3]² [3, −2, 4, −3, 4, 2, −4, −2, −4, 2]
3	3	12	3	[2, −4, −2, 5, 2, 4, −2, 4, 5, −4]
3	3	2	3	[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]
3	3	4	3	[−4, 3, 3, 5, −3, −3, 4, 2, 5, −2] [3, −4, −3, −3, 2, 3, −2, 4, −3, 3]
3	3	6	3	[3, −3, 5, −3, 2, 4, −2, 5, 3, −4]
3	3	4	3	[2, 3, −2, 3, −3; –] [−4, 4, 2, 5, −2]²
3	3	6	3	[5, −2, 2, 4, −2, 5, 2, −4, −2, 2]
3	3	8	3	[2, 5, −2, 5, 5]² [2, 4, −2, 3, 4; –]
3	4	48	3	[5, −3, −3, 3, 3]²
3	4	8	4	[5, −4, 4, −4, 4]² [5, −4, −3, 3, 4, 5, −3, 4, −4, 3]
3	4	4	4	[5, −4, 4, 5, 5]² [−3, 4, −3, 3, 4; –] [4, −3, 4, 4, −4; –] [−4, 3, 5, 5, −3, 4, 4, 5, 5, −4]
3	4	20	4	[5]¹⁰ [−3, 3]⁵ [5, 5, −3, 5, 3]²
3	4	20	4	[−4, 4, −3, 5, 3]²	Pentagonal prism, G_{5, 2}
2	5	120	4		Petersen graph

12 vertices

diam.	girth	Aut.	connect.	LCF	names	picture
6	3	16	1		Edge list 0–1, 0–2, 0–11, 1–2, 1–6, 2–3, 3–4, 3–5, 4–5, 4–6, 5–6, 7–8, 7–9, 7–11, 8–9, 8–10, 9–10, 10–11
5	3	16	1		Edge list 0–1, 0–6, 0–11, 1–2, 1–3, 2–3, 2–5, 3–4, 4–5, 4–6, 5–6, 7–8, 7–9, 7–11, 8–9, 8–10, 9–10, 10–11
6	3	8	1		Edge list 0–1, 0–3, 0–11, 1–2, 1–6, 2–3, 2–5, 3–4, 4–5, 4–6, 5–6, 7–8, 7–9, 7–11, 8–9, 8–10, 9–10, 10–11
5	3	32	1		Edge list 0–1, 0–6, 0–11, 1–2, 1–4, 2–3, 2–5, 3–4, 3–6, 4–5, 5–6, 7–8, 7–9, 7–11, 8–9, 8–10, 9–10, 10–11
5	3	4	2	[3, −2, −4, −3, 4, 2]² [4, 2, 3, −2, −4, −3; –]
4	3	8	2	[3, −2, −4, −3, 3, 3, 3, −3, −3, −3, 4, 2]
4	3	4	2	[4, 2, 3, −2, −4, −3, 2, 3, −2, 2, −3, −2]
4	4	64	2	[3, 3, 3, −3, −3, −3]²
4	3	16	2	[2, −3, −2, 3, 3, 3; –]
4	3	16	2	[2, 3, −2, 2, −3, −2]²
4	3	2	2	[−2, 3, 6, 3, −3, 2, −3, −2, 6, 2, 2, −2] [4, 2, −4, −2, −4, 6, 2, 2, −2, −2, 4, 6]
4	3	8	2	[6, 3, 3, 4, −3, −3, 6, −4, 2, 2, −2, −2]
5	3	4	2	[4, 2, 3, −2, −4, −3, 5, 2, 2, −2, −2, −5]
4	3	16	2	[−3, −3, −3, 5, 2, 2; –]
4	3	8	2	[2, −3, −2, 5, 2, 2; –]
4	3	4	2	[2, 4, −2, 3, −5, −4, −3, 2, 2, −2, −2, 5] [5, 2, −4, −2, −5, −5, 2, 2, −2, −2, 4, 5]
4	3	4	2	[−2, −2, 4, 4, 4, 4; –] [3, −4, −4, −3, 2, 2; –] [5, 3, 4, 4, −3, −5, −4, −4, 2, 2, −2, −2]
4	3	2	2	[4, −2, 4, 2, −4, −2, −4, 2, 2, −2, −2, 2] [5, −2, 2, 3, −2, −5, −3, 2, 2, −2, −2, 2]
5	3	16	2	[2, 2, −2, −2, −5, 5]²
4	3	8	2	[−2, −2, 4, 5, 3, 4; –]
4	3	4	2	[5, 2, −3, −2, 6, −5, 2, 2, −2, −2, 6, 3]
4	3	8	2	[4, −2, 3, 3, −4, −3, −3, 2, 2, −2, −2, 2]
4	3	8	2	[−2, −2, 5, 3, 5, 3; –] [−2, −2, 3, 5, 3, −3; –]
5	3	32	2	[2, 2, −2, −2, 6, 6]²
4	3	8	2	[−3, 2, −3, −2, 2, 2; –]
4	3	8	2	[−2, −2, 5, 2, 5, −2; –]
4	3	8	2	[6, −2, 2, 2, −2, −2, 6, 2, 2, −2, −2, 2]
4	3	48	2	[−2, −2, 2, 2]³
4	3	4	3	[2, 3, −2, 3, −3, 3; –] [−4, 6, 4, 2, 6, −2]²
4	3	4	3	[−4, 6, 3, 3, 6, −3, −3, 6, 4, 2, 6, −2] [−2, 3, −3, 4, −3, 3, 3, −4, −3, −3, 2, 3]
4	3	1	3	[−5, 2, −3, −2, 6, 4, 2, 5, −2, −4, 6, 3] [−2, 3, −3, 4, −3, 4, 2, −4, −2, −4, 2, 3] [3, −2, 3, −3, 5, −3, 2, 3, −2, −5, −3, 2]
3	3	4	3	[−5, −5, 4, 2, 6, −2, −4, 5, 5, 2, 6, −2] [4, −2, 3, 4, −4, −3, 3, −4, 2, −3, −2, 2]
3	3	8	3	[−5, −5, 3, 3, 6, −3, −3, 5, 5, 2, 6, −2] [2, 4, −2, 3, 5, −4, −3, 3, 3, −5, −3, −3]
4	3	2	3	[2, 4, −2, 3, 6, −4, −3, 2, 3, −2, 6, −3] [2, 4, −2, 3, 5, −4, −3, 4, 2, −5, −2, −4] [−5, 2, −3, −2, 5, 5, 2, 5, −2, −5, −5, 3]
4	3	2	3	[−5, 2, −3, −2, 6, 3, 3, 5, −3, −3, 6, 3] [4, −2, −4, 4, −4, 3, 3, −4, −3, −3, 4, 2] [−3, 3, 3, 4, −3, −3, 5, −4, 2, 3, −2, −5]
4	3	2	3	[2, 3, −2, 4, −3, 6, 3, −4, 2, −3, −2, 6] [−4, 5, −4, 2, 3, −2, −5, −3, 4, 2, 4, −2]
4	3	1	3	[6, 3, −4, −4, −3, 3, 6, 2, −3, −2, 4, 4] [−5, −4, 4, 2, 6, −2, −4, 5, 3, 4, 6, −3] [3, 4, 4, −3, 4, −4, −4, 3, −4, 2, −3, −2] [4, 5, −4, −4, −4, 3, −5, 2, −3, −2, 4, 4] [4, 5, −3, −5, −4, 3, −5, 2, −3, −2, 5, 3]
3	4	4	3	[4, 6, −4, −4, −4, 3, 3, 6, −3, −3, 4, 4] [−5, −4, 3, 3, 6, −3, −3, 5, 3, 4, 6, −3] [4, −3, 5, −4, −4, 3, 3, −5, −3, −3, 3, 4]
3	4	16	3	[3, 3, 4, −3, −3, 4; –] [3, 6, −3, −3, 6, 3]²
4	3	1	3	[4, −2, 5, 2, −4, −2, 3, −5, 2, −3, −2, 2] [5, −2, 2, 4, −2, −5, 3, −4, 2, −3, −2, 2] [2, −5, −2, −4, 2, 5, −2, 2, 5, −2, −5, 4]	Frucht graph
4	3	4	3	[−2, 6, 2, −4, −2, 3, 3, 6, −3, −3, 2, 4] [−2, 2, 5, −2, −5, 3, 3, −5, −3, −3, 2, 5]
4	3	2	3	[2, 4, −2, 6, 2, −4, −2, 4, 2, 6, −2, −4] [2, 5, −2, 2, 6, −2, −5, 2, 3, −2, 6, −3]
4	3	2	3	[6, 3, −3, −5, −3, 3, 6, 2, −3, −2, 5, 3] [3, 5, 3, −3, 4, −3, −5, 3, −4, 2, −3, −2] [−5, −3, 4, 2, 5, −2, −4, 5, 3, −5, 3, −3]
4	4	12	3	[3, −3, 5, −3, −5, 3, 3, −5, −3, −3, 3, 5]
4	3	2	3	[4, 2, 4, −2, −4, 4; –] [3, 5, 2, −3, −2, 5; –] [6, 2, −3, −2, 6, 3]²
4	3	2	3	[3, 6, 4, −3, 6, 3, −4, 6, −3, 2, 6, −2] [4, −4, 5, 3, −4, 6, −3, −5, 2, 4, −2, 6] [−5, 5, 3, −5, 4, −3, −5, 5, −4, 2, 5, −2]
3	3	1	3	[6, −5, 2, 6, −2, 6, 6, 3, 5, 6, −3, 6] [6, 2, −5, −2, 4, 6, 6, 3, −4, 5, −3, 6] [5, 5, 6, 4, 6, −5, −5, −4, 6, 2, 6, −2] [−4, 4, −3, 3, 6, −4, −3, 2, 4, −2, 6, 3] [6, 2, −4, −2, 4, 4, 6, 4, −4, −4, 4, −4] [−3, 2, 5, −2, −5, 3, 4, −5, −3, 3, −4, 5] [−5, 2, −4, −2, 4, 4, 5, 5, −4, −4, 4, −5]
3	3	2	3	[2, 6, −2, 5, 6, 4, 5, 6, −5, −4, 6, −5] [5, 6, −4, −4, 5, −5, 2, 6, −2, −5, 4, 4] [2, 4, −2, −5, 4, −4, 3, 4, −4, −3, 5, −4] [2, −5, −2, 4, −5, 4, 4, −4, 5, −4, −4, 5]
4	3	4	3	[2, 4, −2, −5, 5]² [−5, 2, 4, −2, 6, 3, −4, 5, −3, 2, 6, −2]
4	3	2	3	[−4, −4, 4, 2, 6, −2, −4, 4, 4, 4, 6, −4] [−4, −3, 4, 2, 5, −2, −4, 4, 4, −5, 3, −4] [−3, 5, 3, 4, −5, −3, −5, −4, 2, 3, −2, 5]
3	3	2	3	[2, 5, −2, 4, 4, 5; –] [2, 4, −2, 4, 4, −4; –] [−5, 5, 6, 2, 6, −2]² [5, −2, 4, 6, 3, −5, −4, −3, 2, 6, −2, 2]
3	3	2	3	[3, 6, −4, −3, 5, 6, 2, 6, −2, −5, 4, 6] [2, −5, −2, 4, 5, 6, 4, −4, 5, −5, −4, 6] [5, −4, 4, −4, 3, −5, −4, −3, 2, 4, −2, 4]
4	3	2	3	[6, −5, 2, 4, −2, 5, 6, −4, 5, 2, −5, −2] [−2, 4, 5, 6, −5, −4, 2, −5, −2, 6, 2, 5] [5, −2, 4, −5, 4, −5, −4, 2, −4, −2, 5, 2]
4	3	1	3	[2, −5, −2, 6, 3, 6, 4, −3, 5, 6, −4, 6] [6, 3, −3, 4, −3, 4, 6, −4, 2, −4, −2, 3] [5, −4, 6, −4, 2, −5, −2, 3, 6, 4, −3, 4] [5, −3, 5, 6, 2, −5, −2, −5, 3, 6, 3, −3] [−5, 2, −5, −2, 6, 3, 5, 5, −3, 5, 6, −5] [−3, 4, 5, −5, −5, −4, 2, −5, −2, 3, 5, 5] [5, 5, 5, −5, 4, −5, −5, −5, −4, 2, 5, −2]
3	3	2	3	[5, −3, 6, 3, −5, −5, −3, 2, 6, −2, 3, 5] [2, 6, −2, −5, 5, 3, 5, 6, −3, −5, 5, −5] [5, 5, 5, 6, −5, −5, −5, −5, 2, 6, −2, 5] [4, −3, 5, 2, −4, −2, 3, −5, 3, −3, 3, −3] [5, 5, −3, −5, 4, −5, −5, 2, −4, −2, 5, 3]
4	3	4	3	[2, 4, −2, 5, 3, −4; –] [5, −3, 2, 5, −2, −5; –] [3, 6, 3, −3, 6, −3, 2, 6, −2, 2, 6, −2]
4	3	2	3	[6, 2, −4, −2, −5, 3, 6, 2, −3, −2, 4, 5] [2, 3, −2, 4, −3, 4, 5, −4, 2, −4, −2, −5] [−5, 2, −4, −2, −5, 4, 2, 5, −2, −4, 4, 5]
3	3	2	3	[5, 2, 5, −2, 5, −5; –] [6, 2, −4, −2, 4, 6]² [2, −5, −2, 6, 2, 6, −2, 3, 5, 6, −3, 6] [−5, −2, 6, 6, 2, 5, −2, 5, 6, 6, −5, 2]
3	3	12	3	[−5, 3, 3, 5, −3, −3, 4, 5, −5, 2, −4, −2]
3	3	2	3	[6, −4, 3, 4, −5, −3, 6, −4, 2, 4, −2, 5] [−4, 6, −4, 2, 5, −2, 5, 6, 4, −5, 4, −5] [5, −5, 4, −5, 3, −5, −4, −3, 5, 2, 5, −2]
4	3	12	3	[−4, 5, 2, −4, −2, 5; –]	Dürer graph
3	3	4	3	[2, 5, −2, 5, 3, 5; –] [6, −2, 6, 6, 6, 2]² [5, −2, 6, 6, 2, −5, −2, 3, 6, 6, −3, 2]
3	3	4	3	[6, −2, 6, 4, 6, 4, 6, −4, 6, −4, 6, 2] [5, 6, −3, 3, 5, −5, −3, 6, 2, −5, −2, 3]
3	3	4	3	[4, −2, 4, 6, −4, 2, −4, −2, 2, 6, −2, 2] [5, −2, 5, 6, 2, −5, −2, −5, 2, 6, −2, 2]
3	3	24	3	[6, −2, 2]⁴	Truncated tetrahedron
3	3	12	3		Tietze's Graph
3	3	36	3	[2, 6, −2, 6]³
4	4	24	4	[−3, 3]⁶ [3, −5, 5, −3, −5, 5]²	G_{6, 2}, Y₆
3	4	4	4	[6, −3, 6, 6, 3, 6]² [6, 6, −5, 5, 6, 6]² [3, −3, 4, −3, 3, 4; –] [5, −3, 6, 6, 3, −5]² [5, −3, −5, 4, 4, −5; –] [6, 6, −3, −5, 4, 4, 6, 6, −4, −4, 5, 3]
3	4	8	4	[−4, 4, 4, 6, 6, −4]² [6, −5, 5, −5, 5, 6]² [4, −3, 3, 5, −4, −3; –] [−4, −4, 4, 4, −5, 5]²
3	4	2	4	[−4, 6, 3, 6, 6, −3, 5, 6, 4, 6, 6, −5] [−5, 4, 6, 6, 6, −4, 5, 5, 6, 6, 6, −5] [5, −3, 4, 6, 3, −5, −4, −3, 3, 6, 3, −3] [4, −4, 6, 4, −4, 5, 5, −4, 6, 4, −5, −5] [4, −5, −3, 4, −4, 5, 3, −4, 5, −3, −5, 3]
3	4	2	4	[3, 4, 5, −3, 5, −4; –] [3, 6, −4, −3, 4, 6]² [−4, 5, 5, −4, 5, 5; –] [3, 6, −4, −3, 4, 4, 5, 6, −4, −4, 4, −5] [4, −5, 5, 6, −4, 5, 5, −5, 5, 6, −5, −5] [4, −4, 5, −4, −4, 3, 4, −5, −3, 4, −4, 4]
3	4	8	4	[4, −4, 6]⁴ [3, 6, 3, −3, 6, −3]² [−3, 6, 4, −4, 6, 3, −4, 6, −3, 3, 6, 4]	Bidiakis cube
3	4	16	4	[6, −5, 5]⁴ [3, 4, −4, −3, 4, −4]²
3	4	2	4	[−3, 5, −3, 4, 4, 5; –] [4, −5, 5, 6, −4, 6]² [−3, 4, −3, 4, 4, −4; –] [5, 6, −3, −5, 4, −5, 3, 6, −4, −3, 5, 3] [5, 6, 4, −5, 5, −5, −4, 6, 3, −5, 5, −3]
3	4	4	4	[4, −3, 4, 5, −4, 4; –] [4, 5, −5, 5, −4, 5; –] [−5, −3, 4, 5, −5, 4; –]
3	4	2	4	[6, −4, 6, −4, 3, 5, 6, −3, 6, 4, −5, 4] [6, −4, 3, −4, 4, −3, 6, 3, −4, 4, −3, 4] [5, 6, −4, 3, 5, −5, −3, 6, 3, −5, 4, −3] [5, −5, 4, 6, −5, −5, −4, 3, 5, 6, −3, 5] [5, 5, −4, 4, 5, −5, −5, −4, 3, −5, 4, −3]
3	4	4	4	[6, −3, 5, 6, −5, 3, 6, −5, −3, 6, 3, 5] [3, −4, 5, −3, 4, 6, 4, −5, −4, 4, −4, 6]
3	4	8	4	[5, 6, 6, −4, 5, −5, 4, 6, 6, −5, −4, 4]
3	5	16	4	[4, −5, 4, −5, −4, 4; –]
3	4	4	4	[6, 4, 6, 6, 6, −4]² [−3, 4, −3, 5, 3, −4; –] [−5, 3, 6, 6, −3, 5, 5, 5, 6, 6, −5, −5] [−3, 3, 6, 4, −3, 5, 5, −4, 6, 3, −5, −5]
4	4	8	4	[3, 5, 5, −3, 5, 5; –] [−3, 5, −3, 5, 3, 5; –] [5, −3, 5, 5, 5, −5; –]
3	4	48	4	[5, −5, −3, 3]³ [−5, 5]⁶	Franklin graph
3	4	24	4	[6]¹² [6, 6, −3, −5, 5, 3]²
3	5	18	4	[6, −5, −4, 4, −5, 4, 6, −4, 5, −4, 4, 5]

The LCF entries are absent above if the graph has no Hamiltonian cycle, which is rare (see Tait's conjecture). In this case a list of edges between pairs of vertices labeled 0 to n−1 in the third column serves as an identifier.

Vector coupling coefficients

Each 4-connected (in the above sense) simple cubic graph on $2 n$ vertices defines a class of quantum mechanical $3 n$ -j symbols. Roughly speaking, each vertex represents a 3-jm symbol, the graph is converted to a digraph by assigning signs to the angular momentum quantum numbers $j$ , the vertices are labelled with a handedness representing the order of the three $j$ (of the three edges) in the 3-jm symbol, and the graph represents a sum over the product of all these numbers assigned to the vertices.

There are 1 (6-j), 1 (9-j), 2 (12-j), 5 (15-j), 18 (18-j), 84 (21-j), 607 (24-j), 6100 (27-j), 78824 (30-j), 1195280 (33-j), 20297600 (36-j), 376940415 (39-j) etc. of these (sequence A175847 in the OEIS ).

If they are equivalent to certain vertex-induced binary trees (cutting one edge and finding a cut that splits the remaining graph into two trees), they are representations of recoupling coefficients, and are then also known as Yutsis graphs (sequence A111916 in the OEIS ).

Related Research Articles

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete; see Hamiltonian path problem for details.

In graph theory, a uniquely colorable graph is a $k$ -chromatic graph that has only one possible (proper) $k$ -coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into $k$ independent sets and there is no way to partition them into $k - 1$ independent sets.

In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks exist.

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.

<span class="mw-page-title-main">Desargues graph</span> Distance-transitive cubic graph with 20 nodes and 30 edges

In the mathematical field of graph theory, the Desargues graph is a distance-transitive, cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases.

In the mathematical field of graph theory, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. It was discovered by Marion C. Gray in 1932 (unpublished), then discovered independently by Bouwer 1968 in reply to a question posed by Jon Folkman 1967. The Gray graph is interesting as the first known example of a cubic graph having the algebraic property of being edge but not vertex transitive.

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graph $Q n$ is the graph formed from the vertices and edges of an $n$ -dimensional hypercube. For instance, the cube graph $Q 3$ is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. $Q n$ has $2 n$ vertices, $2 n - 1 n$ edges, and is a regular graph with $n$ edges touching each vertex.

In the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph.

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

In the mathematical field of graph theory, the Dürer graph is an undirected graph with 12 vertices and 18 edges. It is named after Albrecht Dürer, whose 1514 engraving Melencolia I includes a depiction of Dürer's solid, a convex polyhedron having the Dürer graph as its skeleton. Dürer's solid is one of only four well-covered simple convex polyhedra.

In the mathematical field of graph theory, the Frucht graph is a cubic graph with 12 vertices, 18 edges, and no nontrivial symmetries. It was first described by Robert Frucht in 1939.

In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs. In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected.

In the mathematical field of graph theory, the Nauru graph is a symmetric, bipartite, cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.

In the mathematical field of graph theory, the F26A graph is a symmetric bipartite cubic graph with 26 vertices and 39 edges.

In the mathematical field of graph theory, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by H. S. M. Coxeter and Robert Frucht, for the representation of cubic graphs that contain a Hamiltonian cycle. The cycle itself includes two out of the three adjacencies for each vertex, and the LCF notation specifies how far along the cycle each vertex's third neighbor is. A single graph may have multiple different representations in LCF notation.

In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected, planar graphs.

Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that every bipartite polyhedral graph with three edges per vertex has a Hamiltonian cycle.

In the mathematical field of graph theory, a zero-symmetric graph is a connected graph in which each vertex has exactly three incident edges and, for each two vertices, there is a unique symmetry taking one vertex to the other. Such a graph is a vertex-transitive graph but cannot be an edge-transitive graph: the number of symmetries equals the number of vertices, too few to take every edge to every other edge.

References

Yutsis, A. P.; Levinson, I. B.; Vanagas, V. V.; Sen, A. (1962). Mathematical Apparatus of the theory of angular momentum. Israel program for scientific translations. Bibcode:1962mata.book.....Y.
Massot, J.-N.; El-Baz, E.; Lafoucriere, J. (1967). "A general graphical method for angular momentum". Reviews of Modern Physics. 39 (2): 288–305. Bibcode:1967RvMp...39..288M. doi:10.1103/RevModPhys.39.288.
Bussemaker, F. C.; Cobeljic, S.; Cvetkovic, D. M. (1976). "Computer investigations of cubic graphs" (PDF).
Bussemaker, F. C.; Cobeljic, S.; Cvetkovic, D. M.; Seidel, J. J. (1977). "Cubic graphs on <=14 vertices". J. Combin. Theory Ser. B. 23 (2–3): 234–235. doi: 10.1016/0095-8956(77)90034-X .
Frucht, R. (1977). "A canonical representation of trivalent Hamiltonian graphs". Journal of Graph Theory. 1 (1): 45–60. doi:10.1002/jgt.3190010111. MR 0463029.
Clark, L.; Entringer, R. (1983). "Smallest maximally non-Hamiltonian graphs". Per. Mathem. Hungar. 14 (1): 57–68. doi:10.1007/BF02023582. MR 0697357. S2CID 122218690.
Wormald, N. C. (1985). "Enumeration of cyclically 4-connected cubic graphs". Journal of Graph Theory. 9 (4): 563–573. doi:10.1002/jgt.3190090418. MR 0890248.
Bar-Shalom, A.; Klapisch, M. (1988). "NJGRAF - an efficient program for calculation of general recoupling coefficients by graphical analysis, compatible with NJSYM". Comput. Phys. Commun. 50 (3): 375–393. Bibcode:1988CoPhC..50..375B. doi:10.1016/0010-4655(88)90192-0.
Brinkmann, G. (1996). "Fast generation of cubic graphs". Journal of Graph Theory. 23 (2): 139–149. doi:10.1002/(SICI)1097-0118(199610)23:2<139::AID-JGT5>3.0.CO;2-U. MR 1408342.
Fack, V.; Pitre, S. N.; Van der Jeugt, J. (1997). "Calculation of general recoupling coefficients using graphical methods". Comput. Phys. Commun. 101 (1–2): 155–170. Bibcode:1997CoPhC.101..155F. doi:10.1016/S0010-4655(96)00170-1.
Danos, M.; Fano, U. (1998). "Graphical analysis of angular momentum for collision products". Physics Reports. 304 (4): 155–227. Bibcode:1998PhR...304..155D. doi:10.1016/S0370-1573(98)00020-9.
Meringer, M. (1999). "Fast generation of regular graphs and construction of cages". Journal of Graph Theory. 30 (2): 137–146. doi:10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G. MR 1665972.
Van Dyck, D.; Brinkmann, G.; Fack, V.; McKay, B. D. (2005). "To be or not to be Yutsis: Algorithms for the decision problem". Comput. Phys. Commun. 173 (1–2): 61–70. Bibcode:2005CoPhC.173...61V. doi:10.1016/j.cpc.2005.07.008. MR 2179511.
Van Dyck, D.; Fack, V. (2007). "On the reduction of Yutsis graphs". Discrete Math. 307 (11–12): 1506–1515. doi: 10.1016/j.disc.2005.11.088 . MR 2311125.
Aldred, R. E. L.; Van Dyck, D.; Brinkmann, G.; Fack, V.; McKay, B. D. (2009). "Graph structural properties of non-Yutsis graphs allowing fast recognition". Discrete Math. 157 (2): 377–386. doi:10.1016/j.dam.2008.03.020. hdl: 1942/9184 . MR 2479811.
Mathar, Richard J. (2011). "The Wigner graphs up to 12 Vertices". arXiv: 1109.2358 [math-ph].

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.