how many walks go through a given edge

Question

Assume a symmetric matrix g of $0$'s and $1$'s that represents a non-directed graph with N nodes and assume there is an edge between nodes $i$ and $j$ (i.e. $g_{ij} = 1$). I am trying to count how many walks of a given length $p$, that start at node $k$ and finish at node $l$, go through the edge $(ij)$ (or the edge $(ji)$). A typical question I would like to answer would be "the edge $(ij)$ is the edge contributing most to the walks between $k$ and $l$".

By using the properties of $g^{[p]}$, I can compute how many walks of length $p$ go from any node $k$ to any other node $l$, and I can use that to compute how many of these walks go through a given node $i$. But that does not help me to compute how many go through a given edge $(ij)$.

I could also compute the number of walks from $k$ to $l$ in the original graph, delete the edge between $i$ and $j$ and compute the new number of walks from $k$ to $l$. However this does not help because I am looking for a systematic way of finding these numbers, I cannot test every edge one by one.

Any idea ? Thank you very much for your attention!

Answer 1

Hint:

• Consider the number of walks $k \xrightarrow{W} l$ in $G' = \langle V, E' \rangle$ where $E' = E \setminus \big\{(i,j), (j,i)\big\}$.

I hope this helps $\ddot\smile$

Answer 2

An idea: Replace the $g_{ij}=1$ of the "critical" edge $\{i,j\}$ by an $x$ and compute the powers $g^p$ as before. The entries of these powers will then be polynomials $P^{(p)}_{kl}(x)$. From $$P^{(p)}_{kl}(x)=a_0+ a_1x+a_2x^2+\ldots+a_p x^p$$ you can infer that there are exactly $a_j$ paths from $k$ to $l$ passing through the critical edge exactly $j$ times.