×

zbMATH — the first resource for mathematics

Fast generation of regular graphs and construction of cages. (English) Zbl 0918.05062
Author’s 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.

MSC:
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Software:
GENREG
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Brinkmann, J Graph Theory 23 pp 139– (1996) · Zbl 0858.05093 · doi:10.1002/(SICI)1097-0118(199610)23:2<139::AID-JGT5>3.0.CO;2-U
[2] Brinkmann, Graph Theory Notes XXXII pp 40– (1997)
[3] and Distance-regular graphs, Springer-Verlag Berlin, 1989. · doi:10.1007/978-3-642-74341-2
[4] and CRC handbook of combinatorial designs, CRC Press, Boca Raton, 1996. · Zbl 0836.00010 · doi:10.1201/9781420049954
[5] Grund, Bayreuther Math Schriften 44 pp 73– (1993)
[6] Grund, Bayreuther Math Schriften 49 pp 1– (1995)
[7] Ein neuer Ansatz zur rekursiven Erzeugung von schlichten Graphen. Master’s thesis, Universität Bayreuth, 1995.
[8] and Algorithms for group actions: Homomorphism principle and orderly generation applied to graphs. DIMACS Series in Discrete Math Theoretical Comp Sci (1995), 113-122.
[9] Hager, Bayreuther Math Schriften 35 pp 157– (1991)
[10] Algebraic combinatorics via finite group actions, Wissenschaftsverlag, Mannheim, (1991). · Zbl 0726.05002
[11] Laue, Bayreuther Math Schriften 43 pp 53– (1993)
[12] Erzeugung regulärer Graphen. Master’s thesis, Universität Bayreuth, (1995).
[13] Read, Ann discr math 2 pp 107– (1978) · Zbl 0392.05001 · doi:10.1016/S0167-5060(08)70325-X
[14] Computation with permutation groups Proc of the Second Symposium on Symbolic and Algebraic Manipulation. (Editor), New York, 1971.
[15] Wong, J Graph Theory 6 pp 1– (1982) · Zbl 0488.05044 · doi:10.1002/jgt.3190060103
[16] Yang, J Math Res Expo 9 pp 628– (1989)
[17] Anti-directed walks in 4-valent graphs, Preprint, University of Ljubljana, 1996.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.