A note on girth-diameter cages

Abstract

In this paper, we introduce a problem closely related to the Cage Problem and the Degree Diameter Problem. For integers $k\ge 2$, $g\ge 3$ and $d\ge 1$, we define a $(k;g,d)$-graph to be a $k$-regular graph with girth $g$ and diameter $d$. We denote by $n_0(k;g,d)$ the smallest possible order of such a graph, and, if such a graph exists, we call it a $(k;g,d)$-cage. In particular, we focus on $(k;5,4)$-graphs. We show that $n_0(k;5,4)\ge k^2+k+2$ for all $k$, and report on the determination of all $(k;5,4)$-cages for $k=3,4$ and $5$ and examples with $k=6$, and describe some examples of $(k;5,4)$-graphs which prove that $n_0(k;5,4)\le 2k^2$ for infinitely many values of $k$.

8 pages, 1 figure