Constructions for cubic graphs with large girth
type: Item
instance of: scholarly article
title: Constructions for cubic graphs with large girth
zbMATH Open document ID: 0911.05036
published in: The Electronic Journal of Combinatorics
publication date: 1999-02-07T00:00:00Z
full work available at URL: https://eudml.org/doc/119715
full work available at URL: v5i1a1.html
review text: 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.
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1247368
zbMATH Keywords: constructing cubic graphs
zbMATH Keywords: large girth
author: Norman L. Biggs
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1247368