0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Just compute the total number of $k$-walks and subtract the total number of $k$-walks in the graph with removed vertex $v$. $\endgroup$ Oct 31, 2015 at 13:55
  • $\begingroup$ 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? $\endgroup$ Oct 31, 2015 at 14:33

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you for your answer! Could you elaborate on (iii) though, please? I do not see the reasoning behind it. $\endgroup$ Oct 31, 2015 at 15:17
  • $\begingroup$ @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$. $\endgroup$ Oct 31, 2015 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.