Regular graphs of large girth and arbitrary degree (Q485001)

The following upper bound for the girth of a \(d\)-regular graph \(G\) is derived from the Moore bound. \[ \text{girth}(G) \leq \left(2 + \frac{2}{\log_{d-1} | G|}\right)\log_{d-1} | G|. \] In this paper, the author investigates the tightness of this bound, constructing, for each \(n\), a family \(G_n\) of \(d+1\)-regular graphs having large girth. More precisely, these \(G_n\) satisfy, for \(d\geq 10\), \(\text{girth}(G_n) \geq \log_d | G_n| \) and if \(d\) is large enough, \(\text{girth}(G_n) \geq 1.33\cdot \log_d | G_n| \). The construction is based on Cayley graphs and the result improves the current bounds given by previous results present in the literature.