Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-29T18:21:06.971Z Has data issue: false hasContentIssue false
  • English
  • Français

Graphs with even girth and small excess

Published online by Cambridge University Press:  24 October 2008

N. L. Biggs  and
T. Ito
N. L. Biggs
Affiliation:
Royal Holloway College, Egham, Surrey TW20 0EX
T. Ito
Affiliation:
Royal Holloway College, Egham, Surrey TW20 0EX
Get access Rights & Permissions [Opens in a new window]

Extract

Let G be a regular graph with even girth g = 2r ≥ 4 and valency k ≥ 3. It is well known, and easy to prove, that G must have at least n0 = n0(g, k) vertices, where

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 88 , Issue 1 , July 1980 , pp. 1 - 10
Copyright
Copyright © Cambridge Philosophical Society 1980

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

REFERENCES

(1)Bannai, E. and Ito, T. Regular graphs with excess one. (To appear.)Google Scholar
(2)Benson, C. T.Minimal regular graphs of girth eight and twelve. Canad. J. Math. 18 (1966), 1091–1094.CrossRefGoogle Scholar
(3)Biggs, N. L.Algebraic Graph Theory (Cambridge University Press, 1974).CrossRefGoogle Scholar
(4)Biggs, N. L.Girth, valency, and excess. Linear Alg. and Appl. (To appear.)Google Scholar
(5)Bollobás, B.Extremal Graph Theory (London, Academic Press, 1978).Google Scholar
(6)Cameron, P. J.Biplanes. Math. Z. 131 (1973), 85–101.CrossRefGoogle Scholar
(7)Cameron, P. J.Parallelisms of Complete Designs. London Math. Soc. Lecture Notes Series no. 23 (Cambridge University Press, 1976).CrossRefGoogle Scholar
(8)Feit, W. and Higman, G.The non-existence of certain generalized polygons. J. Algebra 1 (1964), 114–131.CrossRefGoogle Scholar
(9)Foster, R. M.Geometrical circuits of electrical networks. Trans. Amer. Inst. Elec. Engrs 51 (1932), 309–317.CrossRefGoogle Scholar
(10)Singleton, R. C.On minimal graphs of maximum even girth. J. Combinatorial Theory 1 (1966), 306–332.CrossRefGoogle Scholar