Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-25T17:58:48.006Z Has data issue: false hasContentIssue false
  • English
  • Français

The Smallest Cubic Graphs of Girth Nine

Published online by Cambridge University Press:  12 September 2008

Gunnar Brinkmann ,
Brendan D. Mckay  and
Carsten Saager
Gunnar Brinkmann
Affiliation:
Fakultät für Mathematik, Universität Bielefeld, D 33501 Bielefeld, Germany (e-mail: [email protected])
Brendan D. Mckay
Affiliation:
Department of Computer Science, Australian National University, ACT 0200, Australia (e-mail: [email protected])
Carsten Saager
Affiliation:
Mühlenstr. 7, D 49196 Bad Laer, Germany
Get access Rights & Permissions [Opens in a new window]

Abstract

We describe two computational methods for the construction of cubic graphs with given girth. These were used to produce two independent proofs that the (3,9)-cages, defined as the smallest cubic graphs of girth 9, have 58 vertices. There are exactly 18 such graphs. We also show that cubic graphs of girth 11 must have at least 106 vertices and cubic graphs of girth 13 must have at least 196 vertices.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 4 , Issue 4 , December 1995 , pp. 317 - 329
Copyright
Copyright © Cambridge University Press 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Balaban, A. T. (1973) Trivalent graphs of girth nine and eleven, and relationships among cages. Rev. Roumaine Math. Pures Appl. 18 1033–1043.Google Scholar
[2]Bannai, E. and Ito, T. (1973) On Moore graphs. J. Fac. Sci. Uni. Tokyo Ser. A 20 191–208.Google Scholar
[3]Biggs, N. L. and Hoare, M. J. (1980) A trivalent graph with 58 vertices and girth 9. Discrete Math. 30 299–301.CrossRefGoogle Scholar
[4]Brinkmann, G. (1995) Fast generation of cubic graphs. J. Graph Theory (to appear).3.0.CO;2-U>CrossRefGoogle Scholar
[5]Damerell, R. M. (1973) On Moore graphs. Proc. Cambridge Philos. Soc. 74 227–236.CrossRefGoogle Scholar
[6]Erdős, P. and Sachs, H. (1963) Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl. Wiss. Z. Uni. Halle (Math. Nat.) 12 251–257.Google Scholar
[7]Evans, C. W. (1984) A second trivalent graph with 58 vertices and girth 9. J. Graph Theory 8 97–99.Google Scholar
[8]Frucht, R. (1955) Remarks on finite groups defined by generating relations. Canad. J. Math. 7 8–17.CrossRefGoogle Scholar
[9]McKay, B. D. (1990) nauty Users Guide, Technical Report TR-CS-90–02, Computer Science Department, Australian National University.Google Scholar
[10]McKay, B. D. (1993) Isomorph free exhaustive generation. Preprint.Google Scholar
[11]Read, R. C. (1978) Every one a winner. Annals Discrete Math. 2 107–120.CrossRefGoogle Scholar
[12]Wong, P. K. (1982) Cages – a survey. J. Graph Theory 6 1–22.CrossRefGoogle Scholar