Small graphs and hypergraphs of given degree and girth
type: Item
instance of: scholarly article
title: Small graphs and hypergraphs of given degree and girth
DOI: 10.37236/11765
author: Grahame Erskine
author: James Tuite
published in: The Electronic Journal of Combinatorics
publication date: 2023-04-19T00:00:00Z
full work available at URL: https://arxiv.org/abs/2201.07117
review text: Summary: The search for the smallest possible \(d\)-regular graph of girth \(g\) has a long history, and is usually known as the cage problem. This problem has a natural extension to hypergraphs, where we may ask for the smallest number of vertices in a \(d\)-regular, \(r\)-uniform hypergraph of given (Berge) girth \(g\). We show that these two problems are in fact very closely linked. By extending the ideas of Cayley graphs to the hypergraph context, we find smallest known hypergraphs for various parameter sets. Because of the close link to the cage problem from graph theory, we are able to use these techniques to find new record smallest cubic graphs of girths 23, 24, 28, 29, 30, 31 and 32.
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 7676075
zbMATH Keywords: Cayley graphs
zbMATH Keywords: \(d\)-regular graph
zbMATH Keywords: cage problem
zbMATH Keywords: Berge girth
describes a project that uses: GAP
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W4360850255
cites work: Constructions for cubic graphs with large girth
cites work: Cayley, Marty and Schreier hypergraphs
cites work: On regular hypergraphs of high girth
cites work: Dynamic cage survey
cites work: On biregular bipartite graphs of small excess
cites work: The size of bipartite graphs with a given girth
Recommended article: Q4717030
Recommended article: Small vertex-transitive graphs of given degree and girth
Recommended article: Q4697531
Recommended article: Recursive constructions of small regular graphs of given degree and girth
Recommended article: Smallest regular graphs of given degree and diameter
Recommended article: Q4337357
Recommended article: Graphs with small hyperbolicity constant
Recommended article: Sizes of critical graphs with small maximum degrees
Recommended article: Hyperbolic graphs of small complexity
Recommended article: Q3791175
copyright license: Creative Commons Attribution 4.0 International
description: scientific article; zbMATH DE number 7676075