6
$\begingroup$

I am studying graph theory and I am not sure about how the power of the adjacency works. I know that the $k$-th powers of $A$ tell us about connections in the graph, and I can read lengths between a vertex to vertex after taking powers of the adjacency matrix.

My question is: why can powers of the adjacency matrix determine connections in the graph, and how many powers need to determine it?

  • 0
    So say nth power of adjacency is a connected graph. Start with base step that saying when n=1, (P(n) (any nth power of adjacency matrix determines n-th connection in graph), P(1)=A^1 is true (Which means graph is connected, and nth tells length). And go to induction step that P(n)=A^n is true then P(n+1)=A^(n+1) is also true?2012-11-07

1 Answers 1

5

I will give you a hint on how to proceed.

As you mentioned, the entries of the adjacency matrix gives you the connections between vertices. If you take powers, then you are really concatenating walks. The $ij$th entry of the $k$th power of the adjacency matrix tells you the number of walks of length $k$ from vertex $i$ to vertex $j$.

To prove this using induction, try this fact.

To form a walk of length $k+1$ from vertex $i$ to $j$, you must first have a walk of length $k$ from vertex $i$ to some vertex $v$ and then a walk of length $1$ from vertex $v$ to vertex $j$.

  • 0
    This is very helpful. Thank you so much!2012-11-07