Premium
Fast generation of regular graphs and construction of cages
Author(s) -
Meringer Markus
Publication year - 1999
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199902)30:2<137::aid-jgt7>3.0.co;2-g
Subject(s) - combinatorics , mathematics , metric dimension , graph isomorphism , graph homomorphism , chordal graph , vertex (graph theory) , constructive , isomorphism (crystallography) , discrete mathematics , indifference graph , clique sum , 1 planar graph , graph , computer science , line graph , graph power , chemistry , process (computing) , crystal structure , crystallography , operating system
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