3
$\begingroup$

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?

$\endgroup$
1
3
$\begingroup$

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]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.