Constructions for cubic graphs with large girth (Q1276540): Difference between revisions

Summary: 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_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\leq g\leq 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 concerned with what happens when \(g\geq 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 described, 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\leq 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.