Cayley type graphs and cubic graphs of large girth
type: Item
instance of: scholarly article
title: Cayley type graphs and cubic graphs of large girth
zbMATH Open document ID: 0942.05030
DOI: 10.1016/S0012-365X(99)00222-8
author: Chris Parker
author: John N. Bray
author: Peter J. Rowley
published in: Discrete Mathematics
publication date: 2000-08-06T00:00:00Z
review text: 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.
reviewed by: Carl Droms
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 1423736
zbMATH Keywords: cubic graph
zbMATH Keywords: girth
zbMATH Keywords: Cayley graph
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00222-8
OpenAlex ID: W2030729183
description: scientific article; zbMATH DE number 1423736