The diagonal of the third power
Task number: 3916
Suppose that \(G\) is a triangle free graph and \(A\) its adjacency matrix. What are the elements of the main diagonal of \(A^3\), i.e. the third power of \(A\)?
Hint
Recall the relationship of the number of length sequences \(k\) between two vertices to \(k\). the power of its adjacency matrix.
Solution
The elements in \( A^3 \) correspond to walks of length three between the corresponding pairs of vertices. There would be numbers of triangles on the diagonal, and these are assumed to be zero.
