Constructive enumeration of graphs
Gordon Royle · Bulletin of the Australian Mathematical Society · 1988
The production of exhaustive catalogues of small graphs is an integral part of graph theoretic research effort. This thesis considers two different types of graph, and devises construction methods that were used to extend the range of the existing catalogues. The first half of the thesis concentrates on cubic graphs. An orderly algorithm is devised for the construction of cubic graphs and used to construct all the cubic graphs on up to 20 vertices. Two applications of this catalogue are given. The first of these applications is to a problem concerning cycles through 11 vertices in 3-connected cubic graphs which is solved only with the aid of the catalogue. The second application is that of finding all the snarks on up to 22 vertices. The composition of these snarks in terms of the known infinite families is briefly described.