Let $\mathcal{G}$ be a simple (no self-edges) undirected graph with $N$ vertices, and denote $\mathbf{A}$ its adjacency matrix: $A\_{ij}=1$ if there exists an edge between vertex $i$ and vertex $j$.


$\left[\mathbf{A}^k\right]\_{ab}$ will represents the number of walks of length $k$ between vertices $a$ and $b$, in other words, the number of ways to go from $a$ to $b$ in $k$ steps.


Question
--------


Is there a simple way to count the number of walks of length $k$ starting from $a$ that passes via vertex $b$? (the step where it reaches $b$ is irrelevant).


A related question would be, given a random walk starting at $a$ what is the probability that it passes through $b$ at least once in $k$ steps?


I am afraid that these are hard questions to answer if we do not add details about $\mathcal{G}$. If this is the case, I would already find it interesting to know the answer of these questions in the case of $r-$regular graphs: All vertices possess $r$ edges.



Number of walks on a graph passing through a specific vertex
Let matrix $B$ be obtained from $A$ by removing the row and column corresponding to $b$. Then the number of walks of length $k$ starting from $a$ and passing vertex $b$ is given by
$$\mathrm{rowsum}\_a(A^k) - \mathrm{rowsum}\_a(B^k),$$
where $\mathrm{rowsum}\_a$ is the sum of the row corresponding to $a$.


