The well-known Moore bound $M(k,g)$ serves as a universal lower bound for the order of $k$-regular graphs of girth $g$. The excess $e$ of a $k$-regular graph $G$ of girth $g$ and order $n$ is the difference between its order $n$ and the corresponding Moore bound, $e=n - M(k,g) $. We find infinite families of parameters $(k,g)$, $g$ even, for which we show that the excess of any $k$-regular graph of girth $g$ is larger than $4$. This yields new improved lower bounds on the order of $k$-regular graphs of girth $g$ of smallest possible order; the so-called $(k,g)$-cages. We also show that the excess of the smallest $k$-regular graphs of girth $g$ can be arbitrarily large for a restricted family of $(k,g)$-graphs satisfying a very natural additional structural property.
1
Comenius University
Bratislava, Slovakia
2
University of Primorska
Koper, Slovenia
Tatiana Baginová Jajcayová; Slobodan Filipovski; Robert Jajcay. Improved lower bounds for the orders of even girth cages. The electronic journal of combinatorics, Tome 23 (2016) no. 3. doi: 10.37236/6015
@article{10_37236_6015,
author = {Tatiana Baginov\'a Jajcayov\'a and Slobodan Filipovski and Robert Jajcay},
title = {Improved lower bounds for the orders of even girth cages},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {3},
doi = {10.37236/6015},
zbl = {1351.05216},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6015/}
}
TY - JOUR
AU - Tatiana Baginová Jajcayová
AU - Slobodan Filipovski
AU - Robert Jajcay
TI - Improved lower bounds for the orders of even girth cages
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/6015/
DO - 10.37236/6015
ID - 10_37236_6015
ER -
%0 Journal Article
%A Tatiana Baginová Jajcayová
%A Slobodan Filipovski
%A Robert Jajcay
%T Improved lower bounds for the orders of even girth cages
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/6015/
%R 10.37236/6015
%F 10_37236_6015
