Improved lower bounds for the orders of even girth cages (Q727055)

Summary: 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.