| Abstract: | The construction of complete lists of regular graphs up to isomorphism is one of the oldest problems in constructive combinatorics. In this article an efficient algorithm to generate regular graphs with a 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 computing 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 1 h. There exist exactly four (5, 5)‐cages. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 137–146, 1999 |
