I heard that adjacency matrix can be used to calculate the number of k-length paths in a graph. Can't this be used as a way to calculate the number of hamiltonian paths?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
The adjacency matrix does not calculate the number of $k$-length paths in a graph. It calculates the number of $k$-length walks from one vertex to another. (More specifically, the entries of the $n$th power of the adjacency matrix encodes the number of walks). To see the difference between paths and walks, consider any two adjacent vertices not part of a cycle. Then there is exact one path between the two vertices i.e. the edge between them, but there exists an infinite number of walks between them. For example $v_1 \rightarrow v_2 \rightarrow v_1 \rightarrow v_2$ is a walk from $v_1$ to $v_2$ of length $3$. Specifically, paths do not allow repetition of vertices while walks do, therefore this does not in general aid in the computation of Hamiltonian paths or indeed, paths of arbitrary lengths.