2025/03/09 by Eze, L. C., Jajcay, R., Jajcayová, T. +1 · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2503.06466
The Cage Problem requires for a given pair k ≥ 3, g ≥ 3 of integers the determination of the order of a smallest k-regular graph of girth g. We address a more general version of this problem and look for the (k,g)-spectrum of orders of (k,g)-graphs: the (infinite) list of all orders of (k,g)-graphs. By establishing these spectra we aim to gain a better understanding of the structure and properties of (k,g)-graphs and hope to use the acquired knowledge in both determining new orders of smallest k-regular graphs of girth g as well as developing a set of tools suitable for constructions of extremal graphs with additional requirements. We combine theoretical results with computer-based searches, and determine or determine up to a finite list of unresolved cases the (k,g)-spectra for parameter pairs for which the orders of the corresponding cages have already been established.