0
$\begingroup$

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 ?

enter image description here enter image description here enter image description here

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ If it's at most 2 then the vertices that are reached with 1 and 2 edges should belong to G^2 right? The matrix G^2 shows the vertices that are reached with 2 edges only. $\endgroup$ Commented Aug 4, 2016 at 10:01
  • $\begingroup$ 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. $\endgroup$
    – Shagnik
    Commented Aug 4, 2016 at 10:05
  • $\begingroup$ You mean to say that suppose we take cube of G, the matrix of the cubed graph should contain all the vertices with 1, 2 and 3 edges between them but the cube of the matrix of graph G is not necessarily the matrix for a cubed graph and shows only the vertices with only 3 edges between them? $\endgroup$ Commented Aug 4, 2016 at 10:13
  • $\begingroup$ 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$. $\endgroup$
    – Shagnik
    Commented Aug 4, 2016 at 10:16
  • 1
    $\begingroup$ Yes, in the sense that $G^3$ contains $G$ and $G^2$. $\endgroup$
    – Shagnik
    Commented Aug 4, 2016 at 12:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .