Thread: Walks and Matrices

Let G be a graph with vertices (1,2,...,n) and adjacency matrix A= (a subtext ij)

1) Find an expression for the number of walks of the form i-k-j.


I'm puzzled. I thought I had it figured out as:

entry in ik + entry in kj -1

but this did not hold when I looked at graphs with multiple loops. Any thoughts?

Here is another that I can't even figure out where to begin with.

2) Show that the number of walks of length 2 from vertex i to vertex j in G is the ijth entry of the matrix A^2.

I know how to multiply matrices, but I'm not sure how to put it in general terms to help me.

Originally Posted by jaidon

Let G be a graph with vertices (1,2,...,n) and adjacency matrix A= (a subtext ij)

1) Find an expression for the number of walks of the form i-k-j.

I wish I can understand you
What do you mean by i-j-k walk?

2) Show that the number of walks of length 2 from vertex i to vertex j in G is the ijth entry of the matrix A^2.

This is difficult to explain and messy.
But the general theorem is that the number of walks of length k between two verticies is the entry in the adjancey matrix A^k.
Try to think of it like this:
The a_ij entry in the adjancey matrix is the dot product between the i-th row and j-colomum. Thus, since it consists of only 1's and 0's is the sum of these numbers (after the dot product). The sum is the number of the entries which are common to both (otherwise is zero) this is your walk from these two verticies.

as far as i-k-j walk goes this is how the question is written. i assume it means a walk from i to k then to j. not too sure how this fits in with the definition of this particular matrix