A non-existence result for vertex-girth-regular graphs

Abstract

A $k$-regular graph of girth $g$ is called vertex-girth-regular if every vertex is contained in the same number of cycles of length $g$. For integers $n,k,g$ and $\hat{I}»$, we denote such a graph on $n$ vertices in which every vertex lies on exactly $\hat{I}»$ cycles of length $g$ by a $\text{vgr}(n,k,g,\hat{I}»)$-graph. It is well-known that any vertex-girth-regular graph satisfies $\hat{I}»\le \frac{k(k-1{)}^{\lfloor \frac{g}{2}\rfloor }}{2}$. Graphs for which $\hat{I}»$ is close to this bound are of particular interest in connection with the cage problem, since requiring many girth cycles through every vertex is a natural way to isolate highly structured candidates for small regular graphs of prescribed girth. In this paper, we prove that for every $k\ge 3$ and every integer $0<\epsilon \le \frac{k-1}{2}$, there does not exist a $\text{vgr}(n,k,5,\frac{k(k-1{)}^2}{2}-\epsilon )$-graph. Previous non-existence results had already settled all odd girths at least $7$ and very recently also girth $3$, leaving girth $5$ as the only girth for which no non-trivial non-existence result was known. Thus, our result resolves the final remaining case and completes the picture for odd girths.

13 pages, 2 figures