On the existence of (r,g,\chi)-cages

arXiv2304.03825MaRDI QIDQ6432465FDOQ6432465

Authors: G. Araujo-Pardo, Zhanar Berikkyzy, Linda Lesniak 

Publication date: 7 April 2023

Abstract: In this paper, we work with simple and finite graphs. We study a generalization of the emph{Cage Problem}, which has been widely studied since cages were introduced by Tutte cite{T47} in 1947 and after Erd" os and Sachs cite{ES63} proved their existence in 1963. An emph{$(r,g)$-graph} is an $r$-regular graph in which the shortest cycle has length equal to $g$; that is, it is an $r$-regular graph with girth $g$. An emph{$(r,g)$-cage} is an $(r,g)$-graph with the smallest possible number of vertices among all $(r,g)$-graphs; the order of an $(r,g)$-cage is denoted by $n(r,g)$. The Cage Problem consists of finding $(r,g)$-cages; it is well-known that $(r,g)$-cages have been determined only for very limited sets of parameter pairs $(r,g)$. There exists a simple lower bound for $n(r,g)$, given by Moore and denoted by $n_0(r,g)$. The cages that attain this bound are called emph{Moore cages}.

This page was built for publication: On the existence of $(r,g,\chi)$-cages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6432465)