Geodesic
Spectra of Orders for k-Regular Graphs of Girth g
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1115-1125.

Voir la notice de l'article provenant de la source Library of Science

A (k, g)-graph is a k-regular graph of girth g. Given k ≥ 2 and g ≥ 3, infinitely many (k, g)-graphs of infinitely many orders are known to exist. Our goal, for given k and g, is the classification of all orders n for which a (k, g)-graph of order n exists; we choose to call the set of all such orders the spectrum of orders of (k, g)-graphs. The smallest of these orders (the first element in the spectrum) is the order of a (k, g)-cage; the (k, g)-graph of the smallest possible order. The exact value of this order is unknown for the majority of parameters (k, g). We determine the spectra of orders for (2, g), g ≥ 3, (k, 3), k ≥ 2, and (3, 5)-graphs, as well as the spectra of orders of some families of (k, 4)-graphs. In addition, we present methods for obtaining (k, g)-graphs that are larger then the smallest known (k, g)-graphs, but are smaller than (k, g)-graphs obtained by Sauer. Our constructions start from (k, g)-graphs that satisfy specific conditions derived in this paper and result in graphs of orders larger than the original graphs by one or two vertices. We present theorems describing ways to obtain ‘starter graphs’ whose orders fall in the gap between the well-known Moore bound and the constructive bound derived by Sauer and are the first members of an infinite sequence of graphs whose orders cover all admissible orders larger than those of the ‘starter graphs’.
Keywords: cage, k -regular graph, girth, Sauer bound 
@article{DMGT_2021_41_4_a16,
     author = {Jajcay, Robert and Raiman, Tom},
     title = {Spectra of {Orders} for {k-Regular} {Graphs} of {Girth} g},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1115--1125},
     publisher = {mathdoc},
     volume = {41},
     number = {4},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a16/}
}
TY  - JOUR
AU  - Jajcay, Robert
AU  - Raiman, Tom
TI  - Spectra of Orders for k-Regular Graphs of Girth g
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 1115
EP  - 1125
VL  - 41
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a16/
LA  - en
ID  - DMGT_2021_41_4_a16
ER  - 
%0 Journal Article
%A Jajcay, Robert
%A Raiman, Tom
%T Spectra of Orders for k-Regular Graphs of Girth g
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 1115-1125
%V 41
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a16/
%G en
%F DMGT_2021_41_4_a16
Jajcay, Robert; Raiman, Tom. Spectra of Orders for k-Regular Graphs of Girth g. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1115-1125. http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a16/

[1] E. Bannai and T. Ito, On finite Moore graphs, J. Fac. Sci., Univ. Tokyo, Sect. I A 20 (1973) 191–208.

[2] E. Bannai and T. Ito, Regular graphs with excess one, Discrete Math. 37 (1981) 147–158. https://doi.org/10.1016/0012-365X(81)90215-6

[3] R.M. Damerell, On Moore graphs, Proc. Camb. Philos. Soc. 74 (1973) 227–236. https://doi.org/10.1017/S0305004100048015

[4] P. Erdős and H. Sachs, Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe 12 (1963) 251–258.

[5] G. Exoo and R. Jajcay, Dynamic cage survey, Electron. J. Combin. (2008) DS16.

[6] F. Garbe, On graphs with excess or defect 2, Discrete Appl. Math. 180 (2015) 81–88. https://doi.org/10.1016/j.dam.2014.07.022

[7] T.B. Jajcayová, S. Filipovski and R. Jajcay, Counting cycles in graphs with small excess, Lect. Notes Semin. Interdiscip. Mat. (2017) 17–36.

[8] M. Meringer, Fast generation of regular graphs and construction of cages, J. Graph Theory 30 (1999) 137–146. https://doi.org/10.1002/(SICI)1097-0118(199902)30:2¡137::AID-JGT7¿3.0.CO;2-G

[9] M. Meringer, Fast generation of regular graphs and construction of cages . http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html

[10] H. Sachs, Regular graphs with given girth and restricted circuits, J. Lond. Math. Soc. 38 (1963) 423–429. https://doi.org/10.1112/jlms/s1-38.1.423

[11] N. Sauer, Extremaleigenschaften regulärer Graphen gegebener Taillenweite I. and II., Österr. Akad. Wiss., Math.-Naturw. Kl., S.-Ber., Abt. II 176 (1968) 9–25, 27–43.