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:
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 | ? |
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. In [13] Fiol, Mazzuoccolo and Steffen showed that this definition of k-edge-critical is equivalent to the following: a graph G without k-flow is k-edge-critical if, for every edge e of G, removing e yields 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).
In [7] Edita Máčajová and Martin Škoviera showed that a snark is 4-edge-critical if and only if it is critical and that a snark is 4-vertex-critical if and only if it is bicritical. (A snark is critical if the removal of any two adjacent vertices produces a 3-edge-colourable graph and bicritical if the removal of any two distinct vertices produces a 3-edge-colourable graph). Furthermore, in [8] Roman Nedela and Martin Škoviera showed that a snark is irreducible if and only if it is bicritical. (A snark is irreducible if the removal of every edge-cut which is not the set of all edges incident with a vertex yields a 3-edge-colourable graph).
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 |
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 Brinkmann et al. in [1]. In [6] all hypohamiltonian snarks with at least 38 and at most 44 vertices which can be obtained by performing a dot product on two smaller hypohamiltonian snarks were determined. These graphs are also listed in the table.
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 |
38 | ≥51431 | ? |
40 | ≥8820 | ? |
42 | ≥20575458 | ? |
44 | ≥8242146 | ? |
A graph is K2-hamiltonian if the removal of any pair of adjacent vertices yields a hamiltonian graph.
The table below lists all K2-hamiltonian snarks of order at most 36 as well as the snarks which are both K2-hamiltonian and hypohamiltonian. They were determined by Goedgebeur et al. in [14].
Vertices | K2-ham | K2-ham and hypoham |
---|---|---|
10 | 1 | 1 |
12 | 0 | 0 |
14 | 0 | 0 |
16 | 0 | 0 |
18 | 0 | 0 |
20 | 1 | 1 |
22 | 2 | 2 |
24 | 0 | 0 |
26 | 6 | 5 |
28 | 14 | 12 |
30 | 9 | 9 |
32 | 11 | 11 |
34 | 1036 | 936 |
36 | 3849 | 3008 |
A permutation graph is a cubic graph which has a 2-factor that consists of two induced cycles and a permutation snark is a permutation graph which is also a snark. Permutation snarks must be of order 2 mod 4 since otherwise they would have a 2-factor that consists of two even components and therefore be colourable. All known permutation snarks have 8k + 2 vertices (for ≥ 1). It is not known if there exist permutation snarks with 8k + 6 vertices.
The table below lists all non-hamiltonian permutation graphs of order at most 46 as well as the number of permutation snarks among them. Note that non-hamiltonian permutation graphs must have girth at least 5. The lists of permutation snarks up to order 36 were originally determined by Brinkmann et al. in [1]. They were later extended by Goedgebeur and Renders in [15] up to order 46 using a specialised generation algorithm for permutation graphs and they also determined the non-hamiltonian permutation graphs up to that order. The source code of this algorithm can be found here . The 12 permutation snarks on 34 vertices with λc ≥ 5 and the 736 such graphs on 42 vertices are counterexamples to a conjecture of Zhang [11] who conjectured that the Petersen graph is the only cyclically 5-edge-connected permutation graph.
Lists of general permutation graphs (i.e., including the hamiltonian ones) can be found on the cubic graphs page.
Vertices | Non-hamiltonian | Snarks | Snarks with λc ≥ 5 |
---|---|---|---|
10 | 1 | 1 | 1 |
12 | 0 | 0 | 0 |
14 | 0 | 0 | 0 |
16 | 0 | 0 | 0 |
18 | 2 | 2 | 0 |
20 | 0 | 0 | 0 |
22 | 1 | 0 | 0 |
24 | 0 | 0 | 0 |
26 | 64 | 64 | 0 |
28 | 0 | 0 | 0 |
30 | 9 | 0 | 0 |
32 | 0 | 0 | 0 |
34 | 10778 | 10771 | 12 |
36 | 4 | 0 | 0 |
38 | 1848 | 0 | 0 |
40 | 19 | 0 | 0 |
42 | 3131740 | 3128893 | 736 |
44 | 1428 | 0 | 0 |
46 | 678106 | 0 | 0 |
Let r ≥ 2 be a real number, a circular nowhere-zero r-flow in a graph G is a flow in some orientation of G such that the flow value on each edge lies in the interval [1,r-1] and such that the sum of the inner and outer flow in every vertex is zero. The circular flow number of a graph G, denoted by Φ(G), is the infimum of the real numbers r such that G has a circular nowhere-zero r-flow.
The table below lists the circular flow number of all snarks of order at most 36. They were determined in [5] and [12].
Vertices | Φ=4+1/4 | Φ=4+1/3 | Φ=4+1/2 | Φ=4+2/3 | Φ=5 |
---|---|---|---|---|---|
10 | 1 | ||||
18 | 2 | ||||
20 | 6 | ||||
22 | 20 | ||||
24 | 38 | ||||
26 | 57 | 223 | |||
28 | 1258 | 1641 | 1 | ||
30 | 10500 | 17897 | 2 | ||
32 | 60008 | 233042 | 9 | ||
34 | 3627 | 372708 | 3457227 | 25 | |
36 | 199338 | 3339506 | 56628773 | 17 | 98 |
The oddness of a bridgeless cubic graph is the minimum number of odd components in any 2-factor of the graph. Snarks have oddness at least 2. In [2] it was proven that the smallest snarks with oddness 4 and cyclic edge connectivity 4 have 44 vertices and in [9] it was proven that there are exactly 31 snarks on 44 vertices with oddness 4 and cyclic edge connectivity 4. In the latter article also samples of snarks with oddness 4 were determined up to 52 vertices. These can be downloaded in the table below. We refer to [10] for the smallest snarks of oddness 4 with lower connectivity.
Vertices | Oddness 4 |
---|---|
44 | 31 |
46 | ≥484 |
48 | ≥5905 |
50 | ≥66990 |
52 | ≥813773 |
[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, Ars Mathematica Contemporanea, 16(2): 277-298, 2019.
[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, In: VIII Latin-American Algorithms, Graphs and Optimization Symposium, Electronic Notes in Discrete Mathematics, 50:193-198, 2015.
[5] J. Goedgebeur, D. Mattiolo and G. Mazzuoccolo, A unified approach to construct snarks with circular flow number 5, submitted, 2018. Preprint: arXiv:1804.00957.
[6] J. Goedgebeur and C.T. Zamfirescu, On Hypohamiltonian Snarks and a Theorem of Fiorini, Ars Mathematica Contemporanea, 14(2):227-249, 2018.
[7] E. Máčajová and M. Škoviera, Critical and flow-critical snarks coincide, to appear in Discussiones Mathematicae Graph Theory, 9 pages, 2019.
[8] R. Nedela and M. Škoviera, Decompositions and reductions of snarks, Journal of Graph Theory, 22(3):253-279, 1996.
[9] J. Goedgebeur, E. Macajova and M. Skoviera, The smallest nontrivial snarks of oddness 4, to appear in Discrete Applied Mathematics, 38 pages, 2019.
[10] J. Goedgebeur, On the smallest snarks with oddness 4 and connectivity 2, Electronic Journal of Combinatorics, 25(2), 2018.
[11] C.Q. Zhang, Integer flows and cycle covers of graphs, Monographs and Textbooks in Pure and Applied Mathematics, vol. 205, Marcel Dekker Inc., New York, 1997.
[12] J. Goedgebeur, D. Mattiolo and G. Mazzuoccolo, Computational results and new bounds for the circular flow number of snarks, Discrete Mathematics, 343(10):112026, 11 pages, 2020.
[13] M.A. Fiol, G. Mazzuoccolo and E. Steffen, Measures of edge-uncolorability of cubic graphs, Electronic Journal of Combinatorics, 25(4), 2018.
[14] J. Goedgebeur, J. Renders, G. Wiener and C.T. Zamfirescu, K2-Hamiltonian Graphs: II, manuscript, 2022.
[15] J. Goedgebeur and J. Renders, Generation of Cycle Permutation Graphs and Permutation Snarks, manuscript, 2024.