Authors: Leonard Chidiebere Eze, Robert Jajcay, Tatiana Jajcayová, Dominika Závacká
Using the techniques described in our article [1], we have compiled lists of datasets of graphs. Each dataset consists of adjacency matrices formatted for use in GAP.
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.
| Degree | Girth | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
| 3 | 3,3 | 3,4 | 3,5 | 3,6 | 3,7 | 3,8 | 3,9 | 3,10 | 3,11 | 3,12 |
| 4 | 4,3 | 4,4 | 4,5 | 4,6 | 4,7 | 4,8 | ||||
| 5 | 5,3 | 5,4 | 5,5 | 5,6 | 5,7 | |||||
| 6 | 6,3 | 6,4 | ||||||||
| 7 | 7,3 | 7,4 | ||||||||
Note: Green cells correspond to completely determined (k, g)-spectra.
All graphs listed in the table above are also available in graph6 format. Algorithms used in the described methods are provided in the PDF document.
By applying the method described in [2], we identified 123 non-isomorphic (5,7)-graphs of order 270. The adjacency matrices of these graphs, formatted for use in GAP, are provided here.