How to calculate the number of closed walks of length 5 that don't pass through this vertex?

Question

I was wondering how can I calculate the number of closed walks of length 5 starting on a vertex Vi and ending on this same Vi vertex that don't pass through this vertex. The information I have is the adjacency matrix. Thank you!

Answer 1

I'm going to answer but I can't be sure this is correct. The entries $(A^n)_{ij}$ of the $n$th power of the adjacency matrix $A$ count the number of walks that begin in $i$ and end in $j$ of length $n$. We'll denote $\widetilde{A}^n_{ii}$ as the number of length $n$ walks from $v_i$ to $v_i$ that don't pass through $v_i$ in between steps $1$ and $n$. We can find $\widetilde{A}^n_{ii}$ by decomposing every possible way to travel from $v_i$ to $v_i$ into products of $(\widetilde{A}^k)_{ii}(\widetilde{A}^l)_{ii}\cdot\cdot\cdot(\widetilde{A}^m)_{ii}$ for all $(k+l+ ... +m) = n$ such that $k,l,...,m<n$ and subtracting that from $A^n_{ii}$ like so:

$$\widetilde{A}^1_{ii} = A^1_{ii}$$

$$\widetilde{A}^2_{ii} = A^{2}_{ii} - \widetilde{A}^1_{ii}\widetilde{A}^1_{ii}$$

$$\widetilde{A}^3_{ii} = A^{3}_{ii} - \widetilde{A}^2_{ii}\widetilde{A}^1_{ii} - \widetilde{A}^1_{ii}\widetilde{A}^2_{ii} - \widetilde{A}^1_{ii}\widetilde{A}^1_{ii}\widetilde{A}^1_{ii} = A^{3}_{ii} - 2((A^{2}_{ii} - (A^{1}_{ii})^2)A^1_{ii}) - (A^{1}_{ii})^3$$

$$\widetilde{A}^4_{ii} = A^{4}_{ii} - \widetilde{A}^3_{ii}\widetilde{A}^1_{ii} - \widetilde{A}^2_{ii}\widetilde{A}^2_{ii} - \widetilde{A}^1_{ii}\widetilde{A}^3_{ii} - \widetilde{A}^2_{ii}\widetilde{A}^1_{ii}\widetilde{A}^1_{ii} - \widetilde{A}^1_{ii}\widetilde{A}^2_{ii}\widetilde{A}^1_{ii} - \widetilde{A}^1_{ii}\widetilde{A}^1_{ii}\widetilde{A}^2_{ii} - (\widetilde{A}^1_{ii})^4$$

$$ = A^{4}_{ii} - 2[(A^{3}_{ii} - 2((A^{2}_{ii} - (A^{1}_{ii})^2)A^1_{ii}) - (A^{1}_{ii})^3)(A^1_{ii})] - (A^{2}_{ii} - (A^{1}_{ii})^2)^2 - 3[(A^{2}_{ii} - (A^{1}_{ii})^2)({A}^1_{ii})^2] - ({A}^1_{ii})^4$$

$$\widetilde{A}^5_{ii} = A^{5}_{ii} - ...$$

I'm not going to write out the last part, but I hope you can see where this is going. With the first four equations, you should be able to write something for the 5-walk that can be simplified to an expression that can be computed with powers of $A$.

Answer 2

The number of edges transversed before reaching the vertex can be $2$ or $3$ and it can't be both ( you also can't visit the vertex more than once.

Hence the answer is $A^5_{ii} - A^3_{ii}A^2_{ii} - A^2_{ii}A^3_{ii}$