Fast Generation of Regular Graphs and Construction of Cages

The construction of complete lists of regular graphs up to isomorphism is one of the oldest problems in constructive combinatorics. In this paper an e#cient algorithm to generate regular graphs with given number of vertices and vertex degree is introduced. The method is based on orderly generation refined by criteria to avoid isomorphism checking and combined with a fast test for canonicity. The implementation allows to compute even large classes of graphs, like construction of the 4-regular graphs on 18 vertices and, for the first time, the 5-regular graphs on 16 vertices. Also in cases with given girth some remarkable results are obtained. For instance the 5-regular graphs with girth 5 and minimal number of vertices were generated in less than one hour. There exist exactly four (5,5)-cages