What is the relation between $A(G)$ and $A(G^2)$?
Where $G^2$ is the square of a graph $G$ and $A(G^2),A(G)$ their respective adjacency matrix.
$\endgroup$ 21 Answer
$\begingroup$$G^2$ is the graph with the same set of vertices as $G$, but with edges connecting vertices with distance $\leq 2$ in $G$.
$A(G)$ shows which vertices in $G$ have a distance of 1. $A(G^2)$ shows which vertices in $G^2$ have a distance of $1$, or a distance of $\leq 2$ in $G$.
So, $A(G^2) - A(G)$ shows which vertices in $G$ have a distance of exactly 2. This difference would have non-zero, non-diagonal entries in the same places as $[A(G)]^2$ (where $A_{ij}^{2}$ is the number of walks of length $2$ between vertices $i$ and $j$).
$\endgroup$ 1
