Theoretical and Computational Approaches to Determining Sets of Orders for ( k , g ) (k,g) -Graphs

Leonard Chidiebere Eze a , c, Robert Jajcay a , c, Tatiana Jajcayová b , c, Dominika Závacká b , c · 2025

Read Theoretical and Computational Approaches to Determining Sets of Orders for ( k , g ) (k,g) -Graphs by Leonard Chidiebere Eze a , c, Robert Jajcay a , c, Tatiana Jajcayová b , c, Dominika Závacká b , c (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-06466.txt.

Introduction

Leonard Chidiebere Eze and co-authors work on the cage problem, a classic puzzle in graph theory, in a 2025 paper. A cage is the smallest network where each point has a fixed number of links and the shortest loop has a set length. The authors chase a broader goal: the full list of possible sizes for such networks, for each pair of settings.

They mix proofs with computer searches to pin down those lists, or narrow them to a few open cases. They focus on pairs where the smallest network is already known. The tools they build may help find new record-small networks and design extreme networks with extra demands.

Catalog record

CREATORLeonard Chidiebere Eze a , c, Robert Jajcay a , c, Tatiana Jajcayová b , c, Dominika Závacká b , c
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-06466

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Theoretical and Computational Approaches to Determining Sets of Orders for ( k , g ) (k,g) -Graphs Leonard Chidiebere Eze a , c, Robert Jajcay a , c, Tatiana Jajcayová b , c, Dominika Závacká b , c Abstract The Cage Problem requires for a given pair k ⩾ 3 , g ⩾ 3 k\geqslant 3,g\geqslant 3 of integers the determination of the order of a smallest k k -regular graph of girth g g . We address a more general version of this problem and look for the ( k , g ) (k,g) -spectrum of orders of ( k , g ) (k,g) -graphs: the (infinite) list of all orders of ( k , g ) (k,g) -graphs. By establishing these spectra we aim to gain a better understanding of the structure and properties of ( k , g ) (k,g) -graphs and hope to use the acquired knowledge in both determining new orders of smallest k k -regular graphs of girth g 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 ) (k,g) -spectra for parameter pairs for which the orders of the corresponding cages have already been established. 1 Introduction The Cage Problem is a problem in Extremal Graph Theory that calls for finding a smallest k -regular graph of girth g (with the graphs referred to as (k,g) -graphs ) together with its order n(k,g) , for all pairs k\geqslant 3,g\geqslant 3 . Even though the problem has been around since the 1960’s [ 19 ] , and even though it has received a considerable attention, we only know the exact value of n(k,g) and the corresponding smallest (k,g) -graphs for a rather slim set of parameters [ 7 ] . The problem is universally acknowledged to be hard, and there is no unifying theory behind it. The resolved cases are the result of a number of unrelated constructions and proving the extremality of any specific (k,g) -graph is in fact the core of the complexity of the problem. A natural lower bound on the orders of a (k,g) -graph is referred to as the Moore bound M(k,g) , and is expressed as M(k,g)=\left\{\begin{array}[]{cc}1+\sum_{i=0}^{\frac{g-3}{2}}k(k-1)^{i},&g\penalty\ \text{odd},\\ \\ 2\sum_{i=0}^{\frac{g-2}{2}}(k-1)^{i},&g\penalty\ \text{even}.\end{array}\right. (1) Maybe specifically due to its complexity, the Cage Problem problem has garnered significant attention [ 7 ] . While much research has focused on finding individual cages, or at least on finding smaller (k,g) -graphs than those found by anybody else (called record (k,g) -graphs ), in our work we take a broader approach and study the entire set of orders of (k,g) -graphs for a given (k,g) pair. Given the complexity of the original Cage Problem, our approach might appear futile. Clearly, determining the entire set of orders for a class of graphs for which we cannot even determine the order of its smallest member does not seem particularly promising. Nevertheless, we maintain that taking a broader view and studying the entire class of (k,g) -graphs (instead of just those that stand a chance of being cages) might eventually bring progress even for the question about the smallest order n(k,g) . Moreover, the idea of determining all the orders of (k,g) -graphs goes back to the funding fathers of the topic. Namely, Erdős and Sachs [ 6 ] proved already in 1963 that k -regular graphs of girth at least g and of order 2m exist for all k\geqslant 2 , g\geqslant 3 and m\geqslant 2\sum_{t=1}^{g-2}(k-1)^{t} . A further improvement by Sauer [ 25 ] , 1967, pushes the bound further down and specifically asserts the existence of (k,g) -graphs of all admissible orders greater than or equal to 2(k-1)^{g-2} , in case of odd g , and 4(k-1)^{g-3} for g even (the reader should always keep in mind that the order of an odd degree regular graph must be even, and hence, for odd degrees k , only even order (k,g) -graphs might exist). Based on these classical results, one can already conclude that for any given pair k\geqslant 3 and g\geqslant 3 there must exist an order N such that a (k,g) -graph of order n exists for all n\geqslant N (all even orders if k is odd). We shall denote the smallest N with this property by N(k,g) , and observe that our choice of notation implies the non-existence of a (k,g) -graph of order N(k,g)-1 , for even k , or order N(k,g)-2 , for odd k . It is important to note that N(k,g) is not necessarily equal to n(k,g) as is demonstrated in case of the (3,8) -graphs where n(3,8) is known to be equal to 30 , but it has long been known that no (3,8) -graph of order 32 exists. Thus, N(3,8)\geqslant 34 , and in fact, as shown later, N(3,8)=34 . Algorithmically, this means that determining the entire spectrum of orders of (k,g) -graphs is essentially a finite task; provided one knows the number N(k,g) and is able to search the entire (finite) space of (k,g) -graphs of orders smaller than N(k,g) . The aim of our paper is completing this task for specific relatively small pairs (k,g) by developing a set of tools and constructions possibly applicable for other parameter pairs as well. Before closing the introductory section, let us mention one more (perhaps far fetched) argument for studying the spectra of orders of (k,g) -graphs. A (k,g) -graph of order M(k,g) (of order matching the Moore bound) is called a Moore graph , and the parameters of all but one Moore graph of odd girth have been known since the beginning of the 1960’s [ 13 ] . The parameters of the ‘missing’ Moore graph are (5,57) , its order would be 3250 , and to this day it is not known whether such a graph exists or not. The clever linear algebra based idea that works for the rest of the degree/girth pairs leaves this case unresolved, and even though a large part of the community might think the graph is impossible (should the graph exist, it would have to be in many aspects different from all the other Moore graphs; specifically, it would have to have a rather small automorphism group [ 20 ] ), no one has been able to come with an argument against its existence (despite some widely shared announcements). The main point of the present paragraph is the observation that while one might not be able to show the nonexistence of a (5,57) -graph of order 3250 , a novel linear algebra or counting (e.g., [ 15 , 16 ] ) based argument may show the impossibility of the existence of a (5,57) -graph of some specific order n larger than 3250 . Should the hypothetical existence of a (5,57) -graph of order 3250 in combination with some of the recursive results developed in this paper (or in the future) imply the existence of a (5,57) -graph of order n , such contradiction would yield the non-existence of a Moore (5,57) -graph. 2 Basic

Read the complete text