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.

A survey on snarks and new results: Products, reducibility and a computer search / Cavicchioli, Alberto; Meschiari, Mauro; Ruini, Beatrice; Spaggiari, Fulvia. - In: JOURNAL OF GRAPH THEORY. - ISSN 0364-9024. - STAMPA. - 28(1998), pp. 57-86.

I documenti presenti in Iris Unimore sono rilasciati con licenza Creative Commons Attribuzione - Non commerciale - Non opere derivate 3.0 Italia, salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Powered by IRIS-about IRIS-Utilizzo dei cookie

 Copyright © 2021