Cayley type graphs and cubic graphs of large girth (Q1972135)

A simple graph is called cubic if all of its vertices have degree three. The girth of a graph is the length of its shortest circuit. The number \(c(g)\) is defined to be \( \min\{|V(\Gamma)|\mid \Gamma\) is a cubic graph of girth \(g\} \). The value of \(c(g)\) is unknown for any \(g>12\). Of course, if \(\Gamma\) is a cubic graph with girth \(g\), then \(|V(\Gamma)|\) is an upper bound for \(c(g)\). By considering Cayley graphs (and a certain type of Schreier coset graphs), the authors construct graphs with given numbers of vertices and ``large'' girth, thus obtaining new upper bounds for the value of \(c(g)\) for certain values of \(g\) between 17 and 32. Many of the calculations were done using MAGMA and GAP. A table of the current state of knowledge of \(c(g)\) for \(g \leq 32\), as well as the authors' new examples, are given in an appendix.