# Square and cube of a graph G=(V,E)

CLRS 22.1-5

" The square of a directed graph G=(V,E) is the graph G^2=(V,E^2) such that (u,v) belongs to E^2 if and only G contains a path with at most two edges between u and v. "

I wonder why it's 'at most'. Isn't it that (u,v) belongs to G^2 if and only if G contains a path with 'only' two edges between u and v and on similar lines forG^3?

Here are the matrices from G, G^2and G^3 in its matrix representation. This clearly depicts that it should be 'only' and not 'at most'. Where am I going wrong ?

The square of the graph is defined that way - namely the out-neighbours of a vertex $u$ in the square $G^2$ are the set of vertices you can reach in at most two steps in the original graph $G$.
The adjacency matrix of the squared graph is not the square of the adjacency matrix, although it can be determined from the powers of the adjacency matrix. Note that when you take higher powers, you could start to see entries larger than $1$, or positive entries on the diagonal, which would not correspond to a (simple) directed graph.
• Yes, vertices reached by $1$ edge should also be included. While directed graphs can be represented by matrices, they are not equivalent to their matrices. In particular, the squaring operation is not the same. The adjacency matrix of the squared graph is not the same as the square of the adjacency matrix of the graph. Commented Aug 4, 2016 at 10:05
• It will represent all pairs of vertices with a (directed) path of length at most $3$, yes. Let us call $A$ the adjacency matrix of $G$, and $A_k$ the adjacency matrix of $G^k$. To compute $A_k$, you can take $A + A^2 + A^3 + ... + A^k$ (here we are doing the usual matrix multiplication). Then replace all entries on the main diagonal with $0$, and reduce all positive entries to $1$, to get the $0/1$ adjacency matrix $A_k$ of $G^k$. Commented Aug 4, 2016 at 10:16
• Yes, in the sense that $G^3$ contains $G$ and $G^2$. Commented Aug 4, 2016 at 12:48