What is the relationship between the degree of a regular graph $k$, the number of verticies $v$ and the existence of cycles with length $n$? I am interested if there is a formula for these relationships. I was looking everywhere but I couldn't find anything. Is there some research regarding this topic or is there just no relationship? There is no specific reason for this question. Just curious.
Thank you for your help and time!
 A: The length of the smallest cycle in an $n$-vertex $k$-regular graph is no larger than $2 \log_{k-1} n$; it is open as to whether this bound is tight, in the sense as to whether for $n$ arbitrarily large, is there a $k$-regular graph on $n' \ge n$ vertices where the length of the smallest cycle is at least $(2-o(1))\log_{k-1} n'$. However, for $k$ of the form $k=p^s+1$; $p$ an odd prime, there are explicit constructions that achieve $\frac{4 \log_{k-1} n}{3}$.
Furthermore, let $H_i$; $i=1,2,\ldots$ be the following matrix polynomial:
$H_1(A) = A$; $H_2(A) = A^2-kI$; $H_{2i+2}(A) = AH_{2i+1}(A)-kH_{2i}(A)$.
Then if $A$ is the adjacency matrix of a $k$-regular graph, then $H_i(A)$ is a matrix where the largest eigenvalue is $k(k-1)^{i-1}$, and the sum of its nonzero entries counts the number of closed walks of length $i$. As $H_i(A)$'s largest eigenvalue grows exponentially with $k(k-1)^{i-1}$ it follows that the number of closed walks of length $i$ grows exponentially
in pace with $k-1$ [even for $k$-regular graphs on $n$ vertices where the number of closed walks of length $i$ is 0 for all $i$ up to $\log_{k-1} n$ or so.]
