# Number of walks on a graph passing through a specific vertex

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.

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$$.
• This is undeniably a correct answer to my question, however this would require to know the spectrum of $B$ if one wants to find the number of walks without numerics. Often finding the spectrum of $B$ will be very hard, is there any other method that only relies on the spectrum of $A$?