How to calculate the total number of walks on a directed graph where the start and end vertex is the same, given a length of the walk.
I tried following the answer from Determine the number of different walks of length 4. . From what I understand, it proposes the adjacency matrix to the power of the walk length, but does not consider the same start and end. However, I am not sure I am getting (using numpy) the right answer anyway, given:
A= [[0, 1, 1],
[1, 0, 1],
[1, 1, 0]]
A^3 returns
[[2, 3, 3],
[3, 2, 3],
[3, 3, 2]]
Just doing the combinations manually, I get 2 if considering ending on same vertex, and 4 if not.
$v_1 , v_2 , v_1$
$v_1 , v_3 , v_1$
$v_1 , v_2 , v_3$
$v_1 , v_3 , v_2$
To get only the first case (start on v1 and end on v1), how many walks are possible?