Square of a graph

The square of a graph $G$ is obtained by starting with $G$, and adding edges between any two vertices whose distance in $G$ is $2$.


I would have thought that $G^2$ would either mean the box product of $G$ with itself, or the cross product of $G$ with itself.

The definitions of these are as follows: If $G$ and $H$ are graphs with vertex sets $V_G$ and $V_H$, then the box product of $G$ and $H$ has vertex set $V_G \times V_H$ and has an edge from $(g_1, h_1)$ to $(g_2, h_2)$ if and only if either (1) $g_1=g_2$ and there is an edge from $h_1$ to $h_2$ in $H$ or (2) $h_1=h_2$ and there is an edge from $g_1$ to $g_2$ in $G$.

The cross product of $G$ and $H$ has vertex set $V_G \times V_H$ and has an edge from $(g_1, h_1)$ to $(g_2, h_2)$ if and only if there is an edge from $g_1$ to $g_2$ in $G$ and an edge from $h_1$ to $h_2$ in $H$.

Since TonyK has found yet another definition, I would say that there is more than one thing $G^2$ can denote.

Tags:

Graph Theory