Traces and closed walks that do not close before their time

Question

Let $A$ be the adjacency matrix of a graph. Then, as is well-known and trivial to show, $\mathrm{Tr} A^k$ equals the number of closed walks of length $k$.

Is there a similar way to express (a) the number of closed walks of length $k$ that do not return to their origin before $k$ steps? (b) the number of closed paths or trails of length $k$ (paths being walks that do not repeat vertices, and trails being walks that do not repeat edges)?

---

Let me narrow my question, in part because a closed expression may be hopeless. Say one shows that there are few closed paths of length $\leq 2 k$. Can one give an upper bound on $\mathrm{Tr} A^{2k}$, or on any related quantity, as a result?

Answer 1

I don't think so. Let $a_k$ be the number of paths of length $k$ starting and ending at a particular vertex, and let $b_k$ be the number of such paths who return to their origin for the first time at step $k$. For convenience set $a_0=1$ and $b_0=0$. Then for $n\geq 1$ we have $a_n = \sum_{k=0}^n b_k a_{n-k}$.

Let $A_v(x),B_v(x)$ be the associated generating functions, depending on the chosen vertex. The identity above is $A_v-1=A_vB_v$ and hence $B_v = 1-1/A_v$.

Now $\sum_v A_v(x)=\sum_{k\geq 0} \mathrm{Tr}(A^k)x^k = \mathrm{Tr}\left(\sum_{k\geq 0} A^k x^k\right)$ and we conclude that $$\sum_v A_v(x) = \mathrm{Tr} \left((\mathrm{Id}-Ax)^{-1}\right)\,,$$ but this can't lead to a simple formula for $\sum_v B_v(x)$ in general (you will get a formula when the graph is vertex-transitive).

[Editing to add: counting self-avoiding walks is much harder. Even the asymptotic number of self-avoiding walks in $\mathbb{Z}^d$ is not known precisely, see https://www.math.ubc.ca/~slade/spa_proceedings.pdf]