2024/11/26 by Jan Goedgebeur, Jorik Jooken, Goedgebeur, Jan +3 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #05C07 #05C35 #05C85 #68R10 #90C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2411.17351
openalex publication_date 2024/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An (\r,m\;g)-graph is a (simple, undirected) graph of girth g≥3 with vertices of degrees r and m where 2 ≤ r < m . Given r,m,g, we seek the (\r,m\;g)-graphs of minimum order, called (\r,m\;g)-cages or bi-regular cages, whose order is denoted by n(\r,m\;g). In this paper, we use computational methods for finding (\r,m\;g)-graphs of small order. Firstly, we present an exhaustive generation algorithm, which leads to \unicodex2013 previously unknown \unicodex2013 exhaustive lists of (\r,m\;g)-cages for 24 different triples (r,m,g). This also leads to the improvement of the lower bound of n(\4,5\;7) from 66 to 69. Secondly, we improve 49 upper bounds of n(\r,m\;g) based on constructions that start from r-regular graphs. Lastly, we generalize a theorem by Aguilar, Araujo-Pardo and Berman [arXiv:2305.03290, 2023], leading to 73 additional improved upper bounds.