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.

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email