Snarks

Multiple definitions of snarks exist which vary in strength. In the definition we used, snarks are (simple) cyclically 4-edge connected cubic graphs with chromatic index 4 (i.e. they cannot be properly edge-coloured using 3 colours).

In some definitions snarks are cyclically 5-edge connected or have girth at least 5. But the most important part is the colourability requirement, which is the same in all definitions.

We denote the cyclic edge connectivity of a graph by λc.

The graph lists are currently only available in 'graph6' format. The larger files are compressed with gzip.

The following lists are available:

Snarks

All numbers up to 32 vertices were independently verified by minibaum and snarkhunter. The graphs with more than 32 vertices were generated with snarkhunter. Several conjectures were refuted by these new lists of snarks (see [1] and [2] for more information).

For snarks with 38 vertices and snarks with girth 6 and 40 vertices only a sample was generated as it is currently computationally infeasible to generate the complete lists in these cases (see [3] for more information). The counts of these incomplete cases are indicated with a '≥' in the table. In all other cases the numbers are the counts of the complete sets of snarks.

Vertices girth ≥ 4 girth ≥ 5 girth ≥ 6 girth ≥ 7 λc ≥ 5
10 1 1 0 0 1
12 0 0 0 0 0
14 0 0 0 0 0
16 0 0 0 0 0
18 2 2 0 0 0
20 6 6 0 0 1
22 31 20 0 0 2
24 155 38 0 0 2
26 1297 280 0 0 10
28 12517 2900 1 0 75
30 139854 28399 1 0 509
32 1764950 293059 0 0 2953
34 25286953 3833587 0 0 19935
36 404899916 60167732 1 0 180612
38 ? ≥19775768 39 0 ≥35429
40 ? ? ≥25 0 ?
42 ? ? ? 0 ?

Flow-critical snarks

A graph G without k-flow is k-edge-critical (or k-vertex-critical) if, for every edge e (or for every pair (u,v) of vertices) of G, contracting e (or identifying u and v) yields (without simplifying multiple edges) a graph that has a k-flow.

The table below lists all 4-edge-critical and 4-vertex-critical snarks of order at most 36. They were determined by Carneiro, da Silva and McKay (see [4] for more information).

Vertices girth ≥ 5 Edge-critical Vertex-critical
10 1 1 1
12 0 0 0
14 0 0 0
16 0 0 0
18 2 2 2
20 6 1 1
22 20 2 2
24 38 0 0
26 280 111 111
28 2900 33 33
30 28399 115 115
32 293059 29 13
34 3833587 40330 40328
36 60167732 14548 13720
≤ 36 64326024 55172 54326

Hypohamiltonian snarks

A graph G is hypohamiltonian if G is non-hamiltonian and G-v is hamiltonian for every vertex v of G.

The table below lists all hypohamiltonian snarks of order at most 36. They were determined by Brinkman et al. in [1].

Vertices All λc ≥ 5
10 1 1
12 0 0
14 0 0
16 0 0
18 2 0
20 1 1
22 2 2
24 0 0
26 95 8
28 31 1
30 104 11
32 13 13
34 31198 1497
36 10838 464

References

[1] G. Brinkmann, J. Goedgebeur, J. Hagglund and K. Markstrom, Generation and properties of Snarks, Journal of Combinatorial Theory, Series B, 103(4):468-488, 2013.
[2] J. Goedgebeur, E. Macajova and M. Skoviera, Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44, manuscript, 2017.
[3] G. Brinkmann and J. Goedgebeur, Generation of cubic graphs and snarks with large girth, Journal of Graph Theory, 86(2):255-272, 2017.
[4] A.B. Carneiro, C.N. da Silva and B.D. McKay, A Faster Test for 4-Flow-Criticality in Snarks, VIII Latin-American Algorithms, Graphs and Optimization Symposium, 2015, Beberibe-CE, Brazil. To appear.