Could someone tell me what the "square of a graph" $G^2$ is? Thanks.
$\endgroup$ 33 Answers
$\begingroup$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$.
$\endgroup$ 10 $\begingroup$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.
$\endgroup$ 4 $\begingroup$An oriented graph $G$ is a directed graph with no parallel edges. The square of an oriented graph is a graph $G'$ whose vertex set $V(G')$ is the same as the vertex set $V(G)$ of $G$. An ordered pair of vertices $(u,w)$ is in the arc set $A(G')$ of $G'$ if and only if there exists a vertex $v$ in $G$ (and consequently in $G'$) such that $(u,v)$ and $(v,w)$ are arcs in $G$.
A similar definition for simple graphs may be culled from the above by replacing arcs with edges and ordered pairs of vertices with 2-element subsets of $V(G)$.
$\endgroup$ 1
