A table of small quartic graphs

This page is modeled after the handy wikipedia page Table of simple cubic graphs of “small” connected 3-regular graphs, where by small I mean at most 11 vertices.

These graphs are obtained using the SageMath command graphs(n, [4]*n), where n = 5,6,7,… .

5 vertices: Let $V=\{0,1,2,3,4\}$ denote the vertex set. There is (up to isomorphism) exactly one 4-regular connected graphs on 5 vertices. By Ore’s Theorem, this graph is Hamiltonian. By Euler’s Theorem, it is Eulerian.
4reg5a: The only such 4-regular graph is the complete graph $\Gamma = K_5$ .
graph4reg5
We have

diameter = 1
girth = 3
If G denotes the automorphism group then G has cardinality 120 and is generated by (3,4), (2,3), (1,2), (0,1). (In this case, clearly, $G = S_5$ .)
edge set: $\{(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)\}$

6 vertices: Let $V=\{0,1,\dots, 5\}$ denote the vertex set. There is (up to isomorphism) exactly one 4-regular connected graphs on 6 vertices. By Ore’s Theorem, this graph is Hamiltonian. By Euler’s Theorem, it is Eulerian.
4reg6a: The first (and only) such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 2), (0, 4), (0, 5), (1, 2), (1, 3), (1, 4), (2, 3), (2, 5), (3, 4), (3, 5), (4, 5)\}$ .
graph4reg6
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 48 and is generated by (2,4), (1,2)(4,5), (0,1)(3,5).

7 vertices: Let $V=\{0,1,\dots, 6\}$ denote the vertex set. There are (up to isomorphism) exactly 2 4-regular connected graphs on 7 vertices. By Ore’s Theorem, these graphs are Hamiltonian. By Euler’s Theorem, they are Eulerian.
4reg7a: The 1st such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 3), (0, 5), (0, 6), (1, 2), (1, 3), (1, 5), (2, 3), (2, 4), (2, 6), (3, 4), (4, 5), (4, 6), (5, 6)\}$ . This is an Eulerian, Hamiltonian (by Ore’s Theorem), vertex transitive (but not edge transitive) graph.
graph4reg7a
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 14 and is generated by (1,5)(2,4)(3,6), (0,1,3,2,4,6,5).

4reg7b: The 2nd such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 3), (0, 4), (0, 6), (1, 2), (1, 5), (1, 6), (2, 3), (2, 4), (2, 6), (3, 4), (3, 5), (4, 5), (5, 6)\}$ . This is an Eulerian, Hamiltonian graph (by Ore’s Theorem) which is neither vertex transitive nor edge transitive.
graph4reg7b
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 48 and is generated by (3,4), (2,5), (1,3)(4,6), (0,2)

8 vertices: Let $V=\{0,1,\dots, 7\}$ denote the vertex set. There are (up to isomorphism) exactly six 4-regular connected graphs on 8 vertices. By Ore’s Theorem, these graphs are Hamiltonian. By Euler’s Theorem, they are Eulerian.
4reg8a: The 1st such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 5), (0, 6), (0, 7), (1, 3), (1, 6), (1, 7), (2, 3), (2, 4), (2, 5), (2, 7), (3, 4), (3, 6), (4, 5), (4, 6), (5, 7)\}$ . This is vertex transitive but not edge transitive.
graph4reg8a
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 16 and is generated by $(1,7)(2,3)(5,6)$ and $(0,1)(2,4)(3,5)(6,7)$ .

4reg8b: The 2nd such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 5), (0, 6), (0, 7), (1, 3), (1, 6), (1, 7), (2, 3), (2, 4), (2, 5), (2, 7), (3, 4), (3, 6), (4, 5), (4, 6), (5, 7)\}$ . This is a vertex transitive (but not edge transitive) graph.
graph4reg8b
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 48 and is generated by $(2,3)(5,7)$ , $(1,3)(4,5)$ , $(0,1,3)(4,5,6)$ , $(0,4)(1,6)(2,5)(3,7)$ .

4reg8c: The 3rd such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 2), (0, 5), (0, 6), (1, 3), (1, 4), (1, 7), (2, 3), (2, 4), (2, 7), (3, 5), (3, 6), (4, 5), (4, 6), (5, 7), (6, 7)\}$ . This is a strongly regular (with “trivial” parameters (8, 4, 0, 4)), vertex transitive, edge transitive graph.
graph4reg8c
We have

diameter = 2
girth = 4
If G denotes the automorphism group then G has cardinality $1152=2^7\cdot 3^2$ and is generated by (5,6), (4,7), (3,4), (2,5), (1,2), (0,1)(2,3)(4,5)(6,7).

4reg8d: The 4th such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 2), (0, 4), (0, 6), (1, 3), (1, 5), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 6), (5, 7), (6, 7)\}$ . This graph is not vertex transitive, nor edge transitive.
graph4reg8d
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 16 and is generated by (3,5), (1,4), (0,2)(1,3)(4,5)(6,7), (0,6)(2,7).

4reg8e: The 5th such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 2), (0, 6), (0, 7), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 7), (3, 5), (3, 7), (4, 5), (4, 6), (5, 6), (6, 7)\}$ . This graph is not vertex transitive, nor edge transitive.
graph4reg8e
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 4 and is generated by (0,1)(2,4)(3,6)(5,7), (0,2)(1,4)(3,6).

4reg8f: The 6th (and last) such 4-regular graph is the bipartite graph $\Gamma=K_{4,4}$ having edge set: $\{(0, 1), (0, 2), (0, 6), (0, 7), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 5), (3, 7), (4, 5), (4, 6), (5, 6), (5, 7), (6, 7)\}$ . This graph is not vertex transitive, nor edge transitive.
graph4reg8f
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 12 and is generated by (3,4)(6,7), (1,2), (0,3)(5,6).

9 vertices: Let $V=\{0,1,\dots, 8\}$ denote the vertex set. There are (up to isomorphism) exactly 16 4-regular connected graphs on 9 vertices. Perhaps the most interesting of these is the strongly regular graph with parameters (9, 4, 1, 2) (also distance regular, as well as vertex- and edge-transitive). It has an automorphism group of cardinality 72, and is referred to as d4reg9-14 below.

Without going into details, it is possible to theoretically prove that there are no harmonic morphisms from any of these graphs to either the cycle graph $C_4$ or the complete graph $K_4$ . However, both d4reg9-3 and d4reg9-14 not only have harmonic morphisms to $C_3$ , they each may be regarded as a multicover of $C_3$ .

d4reg9-1
Gamma edges: E1 = [(0, 1), (0, 2), (0, 7), (0, 8), (1, 2), (1, 3), (1, 7), (2, 3), (2, 8), (3, 4), (3, 5), (4, 5), (4, 6), (4, 8), (5, 6), (5, 7), (6, 7), (6, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  12 
aut gp gens:  [(1,2)(4,5)(7,8), (0,1)(3,8)(5,6), (0,4)(1,5)(2,6)(3,7)]

d4reg9_1

d4reg9-2 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 3), (1, 7), (2, 3), (2, 5), (2, 8), (3, 4), (4, 5), (4, 6), (4, 8), (5, 6), (5, 7), (6, 7), (6, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  2 
aut gp gens:  [(0,5)(1,6)(2,8)(3,4)]

d4reg9_2

d4reg9-3 
Gamma edges: E1 = [(0, 1), (0, 2), (0, 7), (0, 8), (1, 2), (1, 3), (1, 4), (2, 3), (2, 8), (3, 4), (3, 5), (4, 5), (4, 6), (5, 6), (5, 7), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  18 
aut gp gens:  [(1,7)(2,8)(3,6)(4,5), (0,1,4,6,8,2,3,5,7)]

d4reg9_3

d4reg9-4 
Gamma edges: E1 = [(0, 1), (0, 5), (0, 7), (0, 8), (1, 2), (1, 4), (1, 7), (2, 3), (2, 4), (2, 5), (3, 4), (3, 6), (3, 8), (4, 5), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  4 
aut gp gens:  [(2,4), (0,6)(1,3)(7,8)]

d4reg9_4

d4reg9-5 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 5), (0, 8), (1, 2), (1, 4), (1, 7), (2, 3), (2, 5), (2, 7), (3, 4), (3, 8), (4, 5), (4, 6), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  12 
aut gp gens:  [(1,5)(2,4)(6,7), (0,1)(2,3)(4,5)(7,8)]

d4reg9_5

d4reg9-6 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 5), (1, 6), (2, 3), (2, 5), (2, 6), (3, 4), (3, 8), (4, 5), (4, 7), (4, 8), (5, 6), (6, 7), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  8 
aut gp gens:  [(2,6)(3,7), (0,3)(1,2)(4,7)(5,6)]

d4reg9_6

d4reg9-7 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 4), (0, 8), (1, 2), (1, 3), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (4, 5), (4, 8), (5, 6), (5, 7), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  2 
aut gp gens:  [(0,3)(1,4)(2,8)(5,6)]

d4reg9_7

d4reg9-8 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 3), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (4, 5), (4, 6), (4, 8), (5, 6), (5, 8), (6, 7), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  2 
aut gp gens:  [(0,8)(1,5)(2,6)(3,4)]

d4reg9_8

d4reg9-9 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 6), (0, 8), (1, 2), (1, 3), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (4, 5), (4, 7), (4, 8), (5, 6), (5, 8), (6, 7), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  4 
aut gp gens:  [(5,7), (0,3)(2,6)(4,8)]

d4reg9_9

d4reg9-10 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 5), (0, 8), (1, 2), (1, 4), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 8), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  16 
aut gp gens:  [(2,6)(3,8), (1,5), (0,1)(2,3)(4,5)(6,8)]

d4reg9_10

d4reg9-11 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 4), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 5), (4, 5), (4, 8), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  8 
aut gp gens:  [(2,4)(7,8), (0,2)(3,7)(4,6)(5,8)]

d4reg9_11

d4reg9-12 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 6), (0, 8), (1, 2), (1, 4), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 8), (5, 6), (5, 8), (6, 7), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  18 
aut gp gens:  [(1,6)(2,5)(3,8)(4,7), (0,1,6)(2,7,3)(4,5,8), (0,2)(1,3)(5,8(6,7)]

d4reg9_12

d4reg9-13 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 4), (0, 8), (1, 2), (1, 5), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 8), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  8 
aut gp gens:  [(2,6)(3,8), (0,1)(2,3)(4,5)(6,8), (0,4)(1,5)]

d4reg9_13

d4reg9-14 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 4), (0, 8), (1, 2), (1, 5), (1, 8), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 6), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  72 
aut gp gens:  [(2,5)(3,4)(6,7), (1,3)(4,8)(5,7), (0,1)(2,3)(4,5)]

d4reg9_14

d4reg9-15 
Gamma edges: E1 = [(0, 1), (0, 4), (0, 6), (0, 8), (1, 2), (1, 3), (1, 5), (2, 3), (2, 4), (2, 7), (3, 4), (3, 7), (4, 5), (5, 6), (5, 8), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  32 
aut gp gens:  [(6,8), (2,3), (1,4), (0,1)(2,6)(3,8)(4,5)]

d4reg9_15

d4reg9-16 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 7), (3, 8), (4, 5), (4, 6), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  16 
aut gp gens:  [(7,8), (4,5), (0,1)(2,3)(4,7)(5,8), (0,2)(1,3)(4,7)(5,8)]

d4reg9_16

10 vertices: Let $V=\{0,1,\dots, 9\}$ denote the vertex set. There are (up to isomorphism) exactly 59 4-regular connected graphs on 10 vertices. One of these actually has an automorphism group of cardinality 1. According to SageMath: Only three of these are vertex transitive, two (of those 3) are symmetric (i.e., arc transitive), and only one (of those 2) is distance regular.

Example 1: The quartic, symmetric graph on 10 vertices that is not distance regular is depicted below. It has diameter 2, girth 4, chromatic number 3, and has an automorphism group of order 320 generated by $\{(7,8), (4,6), (1,2), (1,7)(2,8)(3,4)(5,6), (0,1,3,4,7)(2,5,6,8,9)\}$ .

d4reg10-46a

Example 2: The quartic, distance regular, symmetric graph on 10 vertices is depicted below. It has diameter 3, girth 4, chromatic number 2, and has an automorphism group of order 240 generated by $\{(2,5)(4,7), (2,8)(3,4), (1,5)(7,9), (0,1,3,2,7,6,9,8,4,5)\}$ .

d4reg10-51a

11 vertices: There are (up to isomorphism) exactly 265 4-regular connected graphs on 11 vertices. Only two of these are vertex transitive. None are distance regular or edge transitive.

Example 1: One of the vertex transitive graphs is depicted below. It has diameter 2, girth 4, chromatic number 3, and has an automorphism group of order 22 generated by $\{(1,10)(2,9)(3,4)(5,6)(7,8), (0,1,5,4,2,7,8,9,3,6,10)\}$ .

Example 2:The second vertex transitive graph is depicted below. It has diameter 3, girth 3, chromatic number 4, and has an automorphism group of order 22 generated by $\{(1,5)(2,7)(3,6)(4,8)(9,10), (0,1,3,2,4,10,9,8,7,6,5)\}$ .

One thought on “A table of small quartic graphs”

Pingback: Quartic graphs with 12 vertices | Yet Another Mathblog

Yet Another Mathblog

Share this:

Like this:

Related

One thought on “A table of small quartic graphs”

Leave a Reply Cancel reply