×

Constructions for cubic graphs with large girth. (English) Zbl 0911.05036

Electron. J. Comb. 5, Article A1, 25 p. (1998); printed version J. Comb. 5, 1-25 (1998).
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.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C35 Extremal problems in graph theory
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: EuDML EMIS