On the order-diameter ratio of girth-diameter cages

For integers $k,g,d$, a $(k;g,d)$-cage (or simply girth-diameter cage) is a smallest k-regular graph of girth g and diameter d (if it exists). The order of a $(k;g,d)$-cage is denoted by $n(k;g,d)$. We determine asymptotic lower and upper bounds for the ratio between the order and the diameter of girth-diameter cages as the diameter goes to infinity. We also prove that this ratio can be computed in constant time for fixed k and g. We theoretically determine the exact values $n(3;g,d)$, and count the number of corresponding girth-diameter cages, for g ∈ \4,5\. Moreover, we design and implement an exhaustive graph generation algorithm and use it to determine the exact order of several open cases and obtain -- often exhaustive -- sets of the corresponding girth-diameter cages. The largest case we generated and settled with our algorithm is a $(3;7,35)$-cage of order 136. 23 pages