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.


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.


1 Answer 1


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$.

  • $\begingroup$ 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$? $\endgroup$
    – Sam
    Dec 16, 2021 at 1:32
  • $\begingroup$ I think there is no much simpler method. $\endgroup$ Dec 16, 2021 at 3:32

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.