Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-97-11 September 1997

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 well-defined integer \mu₀(g), the smallest number of vertices for which a cubic graph with girth at least g exists, and furthermore, the minimum value \mu₀(g) is attained by a graph whose girth is exactly g. The values of \mu₀(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^cg_i 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.

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