Let $G = (V,E,W)$ be a weighted graph, where each edge $e = (v\_i,v\_j)$ has weight $w\_{ij} \in \mathbb Z^+ \cup \{0\}$. By replacing $e$ with $w\_{ij}$ copies of unweighted multiedges, a weighted graph $G$ is transferred as an unweighted multigraph. For example, a $2$-walk $v\_0 v\_1 v\_2$ in the weighted graph version will correspond to $(w\_{01} \times w\_{12})$ $2$-walks in the unweighted multigraph version. 


Let $v \in V(G)$. What can one say about the number of $k$-walks containing $v$, with regard to the types of walks, and the number of walks of each type? For instance, in the case of $2$-walks, there are three types of such walks:- (i) Closed $2$-walks containing the vertex $v$, (ii) Non-closed $2$-walks containing the vertex $v$ as one of the end-vertices, (iii) Non-closed $2$-walks containing the vertex $v$ as the middle point. How does one characterize these types in general for $k$-walks and compute the number of walks of each type? 



Number of $k$-walks containing a vertex in an unweighted multigraph
Let $A = (w\_{ij})$ be the (weighted) adjacency matrix of $G$. Then:


(i) the number of closed $k$-walks containing vertex $v\_1$ equals $(A^k)\_{1,1}$;


(ii) the number of non-closed $k$-walks containing $v\_1$ as an end point equals $\sum\_{i\ne 1} (A^k)\_{i,1} + (A^k)\_{1,i}$;


(iii) the number of non-closed $k$-walks containing $v\_1$ equals the sum of non-diagonal elements in $A^k$ minus the sum of non-diagonal elements of $B^k$, where $B$ is obtained from $A$ by removing the first row and column;


(iv) the number of non-closed $k$-walks containing $v\_1$ as a middle point equals the amount in (iii) minus the amount in (ii).


