Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-20T18:37:13.473Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimal Regular Graphs of Girths Eight and Twelve

Published online by Cambridge University Press:  20 November 2018

Clark T. Benson
Clark T. Benson*
Affiliation:
University of Manitoba
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In (3) Tutte showed that the order of a regular graph of degree d and even girth g > 4 is greater than or equal to

Here the girth of a graph is the length of the shortest circuit. It was shown in (2) that this lower bound cannot be attained for regular graphs of degree > 2 for g ≠ 6, 8, or 12. When this lower bound is attained, the graph is called minimal. In a group-theoretic setting a similar situation arose and it was noticed by Gleason that minimal regular graphs of girth 12 could be constructed from certain groups. Here we construct these graphs making only incidental use of group theory. Also we give what is believed to be an easier construction of minimal regular graphs of girth 8 than is given in (2). These results are contained in the following two theorems.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 18 , 1966 , pp. 1091 - 1094
Copyright
Copyright © Canadian Mathematical Society 1966

References

1. Artin, Emil, Geometric algebra (New York, 1957).Google Scholar
2. Singleton, R., Regular graphs of even girth, Ph.D. Thesis, Princeton University (1963).Google Scholar
3. Tutte, W., Proc. Cambridge Philos. Soc. (1947).Google Scholar