Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-97-11

September 1997

Constructions for Cubic Graphs with Large Girth

Norman Biggs


The aim of this paper is to give a coherent account of the problem of constructing cubic graphs with large girth. There is a well-defined integer \mu0(g), the smallest number of vertices for which a cubic graph with girth at least g exists, and furthermore, the minimum value \mu0(g) is attained by a graph whose girth is exactly g. The values of \mu0(g) when 3<=g<=8 have been known for over thirty years. For these values of g each minimal graph is unique and, apart from the case g=7, a simple lower bound is attained.

This paper is mainly a survey of what has been achieved for g>=9, where the situation is quite different. Here it is known that the simple lower bound is attained if and only if g=12. A number of techniques are covered, with emphasis on the construction of families of graphs {Gi} for which the number of vertices ni and the girth gi are such that ni<=2cgi for some finite constant c. The optimum value of c is known to lie between 0.5 and 0.75. At the end of the paper there is a selection of open questions, several of them containing suggestions which might lead to improvements in the known results. There are also some historical notes on the current-best graphs for girth up to 36.

If you would like a free copy of this report, please send the number of this report, LSE-CDAM-97-11, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-171-955 7732.
Fax: +44(0)-171-955 6877.
Email: info@maths.lse.ac.uk

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2005

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html