Closed paths, traces and spectra Let $\Gamma$ be a graph. Write $A$ for its adjacency matrix. It is trivial to show that $\mathrm{Tr} A^k$ equals the number of closed walks of length k, that is, the number of $k$-step walks that return to where they started.
Suppose that we show that $\Gamma$ has few closed paths of length $\leq k$. (A path is a walk without repeated vertices; obviously we are allowing (and requiring) the origin vertex to be the ending vertex.) Can we prove an upper bound on $\mathrm{Tr} A^k$ as a result? If not, can we prove something else about the spectrum of $A$, possibly with additional conditions? (We may, for instance, assume that the degree of $\Gamma$ is very small compared to its number of vertices.)
The same questions can be posed if we show that $\Gamma$ has few closed trails of length $\leq k$. A trail is a walk without repeated edges.
 A: I would put this as a comment but don't have enough (any) reputation...
Closed paths of length $\leq k$ show up when you take the trace of the alternating $k$th power of $A$, which is also equal to
$\sum_{ i_1 < i_2 < \cdots < i_k : } \lambda_{i_1} \cdots \lambda_{i_k}$
where $i_j \in |V(\Gamma)|$ and
$\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_{|V(\Gamma)|}$
are the eigenvalues of the adjacency matrix.
There are always going to be paths of length 2: their contribution to the trace can be expressed in terms of the number of perfect matchings in the graph of different sizes.
You might ask that there are no closed paths of length $2 < L \leq k$. I suspect having few closed paths expresses that the eigenvalues have some kind of `symmetry' expressed by a symmetric polynomial of the eigenvalues being small.
A variant of trails show up if you trace the alternating $k$th power of the non-backtracking operator of the graph as follows.
Namely, say that a closed walk is a weak trail if no edge is traversed more than once in each direction that can be given to the edge (so the edge might be traversed once in each direction).
The non-backtracking operator acts on functions on directed edges of $\Gamma$. A directed edge $e_1$ is `connected' to $e_2$ if the terminus of $e_1$ is the source of $e_2$ but $e_1$ is not $e_2$ with the opposite orientation; note that this is not symmetric. The non-backtracking operator is the adjacency operator of the directed graph $\Gamma^*$ whose vertices are directed edges of $\Gamma$ and directed edges in $\Gamma^*$ are as above.
Note that closed walks in $\Gamma^*$ are in length-preserving one-to-one correspondence with closed non-backtracking walks in $\Gamma$. Closed paths in $\Gamma^*$ are in length-preserving one-to-one correspondence with closed non-backtracking weak trails in $\Gamma$.
Unfortunately, the non-backtracking operator is not self adjoint in general, but if $\Gamma$ is $d$-regular then one can write a Jordan form of the operator in terms of the eigenvalues of the adjacency operator of $\Gamma$ (see e.g. Section 3.1 of the article link of Lubetzky and Peres).
Because the non-backtracking operator is the adjacency operator of $\Gamma^*$, the previous remarks relating the eigenvalues of $\Gamma$ to closed paths also give a relation between some more complicated spectral information of $\Gamma$ and closed non-backtracking weak trails.
Sorry this doesn't exactly answer the question, it was originally intended as a comment.
