Theoretical and Computational Approaches to Determining Sets of Orders for $(k,g)$-Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915188227178496 |
|---|---|
| author | Eze, L. C. Jajcay, R. Jajcayová, T. Závacká, D. |
| author_facet | Eze, L. C. Jajcay, R. Jajcayová, T. Závacká, D. |
| contents | The Cage Problem requires for a given pair $k \geq 3, g \geq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_06466 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Theoretical and Computational Approaches to Determining Sets of Orders for $(k,g)$-Graphs Eze, L. C. Jajcay, R. Jajcayová, T. Závacká, D. Combinatorics Discrete Mathematics The Cage Problem requires for a given pair $k \geq 3, g \geq 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. |
| title | Theoretical and Computational Approaches to Determining Sets of Orders for $(k,g)$-Graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2503.06466 |