On $(k,g)$-Graphs without $(g+1)$-Cycles

Abstract

A $(k,g,\underline{g+1})$-graph is a $k$-regular graph of girth $g$ which does not contain cycles of length $g+1$. Such graphs are known to exist for all parameter pairs $k\ge 3,g\ge 3$, and we focus on determining the orders $n(k,g,\underline{g+1})$ of the smallest $(k,g,\underline{g+1})$-graphs. This problem can be viewed as a special case of the previously studied Girth Pair Problem, the problem of finding the order of a smallest $k$-regular graph in which the length of a smallest even length cycle and the length of a smallest odd length cycle are prescribed. When considering the case of an odd girth $g$, this problem also yields results towards the Cage Problem, the problem of finding the order of a smallest $k$-regular graph of girth $g$. We establish the monotonicity of the function $n(k,g,\underline{g+1})$ with respect to increasing $g$, and present universal lower bounds for the values $n(k,g,\underline{g+1})$. We propose an algorithm for generating all $(k,g,\underline{g+1})$-graphs on $n$ vertices, use this algorithm to determine several of the smaller values $n(k,g,\underline{g+1})$, and discuss various approaches to finding smallest $(k,g,\underline{g+1})$-graphs within several classes of highly symmetrical graphs.

20 pages