Let $\Gamma$ be an undirected finite graph. Write $M_r$ for the number of non-backtracking closed walks of length $r$ in $\Gamma$, i.e., walks where a step is never followed by its inverse. Let $A$ be the adjacency matrix of $\Gamma$, and $\lambda_1,...,\lambda_N$ its eigenvalues.
If $\Gamma$ is regular of degree $d$, then
$$M_{2 k} = (d-1)^k \sum_{n=1}^N \left(U_{2 k}\left(\frac{\lambda_n}{2 \sqrt{d-1}}\right) - \frac{1}{d-1} U_{2 k-2}\left(\frac{\lambda_n}{2 \sqrt{d-1}}\right) \right),$$ where $U_m$ is the $m$th Chebyshev polynomial of the second kind. For a proof, see, e.g., section 1.4 of the Davidoff-Sarnak-Valette monograph.
In particular, if many ($\geq \epsilon N$, say) of the eigenvalues $\lambda_i$ are large ($\geq \Lambda$, where $\Lambda > 5 \sqrt{d}$, say) then, for $k$ not too small, $M_{2 k}$ is large (in fact, roughly in the order of $\epsilon N\cdot \Lambda^{2 k}$).
Is an expression such as the above possible when $\Gamma$ is not regular? Can we at least obtain the conclusion that, if many of the eigenvalues are large ($\geq \Lambda$, where $\Lambda \ggg \sqrt{D}$, and $D$ is the maximal degree of the vertices of $\Gamma$) then $M_{2 k}$ must be large?
(Related, vaguer question: Closed geodesics and eigenvalues in a non-regular graph)
