# Number of $k$-walks containing a vertex in an unweighted multigraph

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?

• Just compute the total number of $k$-walks and subtract the total number of $k$-walks in the graph with removed vertex $v$. Oct 31, 2015 at 13:55
• I'm sorry, I should have phrased the question more explicitly. What I'm looking for is not just the number of such $k$-walks, but also the type. For example, 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? Oct 31, 2015 at 14:33

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).
• @AntonSchigur: It is the same reasoning as in my comment to your question above. The number of non-closed $k$-walks containing $v_1$ equals the total number of non-closed $k$-walks minus the number of non-closed $k$-walks not containing $v_1$. Oct 31, 2015 at 15:29