Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM9711September 1997 
Norman Biggs
Abstract
The aim of this paper is to give a coherent account of the problem of constructing cubic graphs with large girth. There is a welldefined integer \mu_{0}(g), the smallest number of vertices for which a cubic graph with girth at least g exists, and furthermore, the minimum value \mu_{0}(g) is attained by a graph whose girth is exactly g. The values of \mu_{0}(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 {G_{i}} for which the number of vertices n_{i} and the girth g_{i} are such that n_{i}<=2^{cgi} 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 currentbest graphs for girth up to 36.
If you would like a free copy of this report, please send the number of this report, LSECDAM9711, 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)171955 7732. Fax: +44(0)171955 6877. Email: info@maths.lse.ac.uk 
Introduction to the CDAM Research Report Series.  
CDAM Homepage. 
Last changed: Wed 9 Feb 2005
For comments go to:
http://www.maths.lse.ac.uk/webmaster.html