A survey on snarks and new results: Products, reducibility and a computer search

In this paper we survey recent results and problems of both theoretical and algorithmic character on the construction of snarks-non-trivial cubic graphs of class two, of cyclic edge-connectivity at least 4 and with girth greater than or equal to 5. We next study the process, also considered by Cameron, Chetwynd, Watkins, Isaacs, Nedela, and Skoviera, of splitting a snark into smaller snarks which compose it. This motivates an attempt to classify snarks by recognizing irreducible and prime snarks and proving that all snarks can be constructed from them. As a consequence of these splitting operations, it follows that any snark (other than the Petersen graph) of order less than or equal to 26 can be built as either a dot product or a square product of two smaller snarks. Using a new computer algorithm we have confirmed the computations of Brinkmann and Steffen on the classification of all snarks of order less than 30. Our results recover the well-known classification of snarks of order not exceeding 22. Finally, we prove that any snark G of order less than or equal to 26 is almost Hamiltonian, in the sense that G has at least one vertex v for which G\v is Hamiltonian.