7
$\begingroup$

Could someone tell me what the "square of a graph" $G^2$ is? Thanks.

  • 1
    There are unusually many different species of "graph product". I think there is even a book with this as the title...(See David's answer below for an acknowledgment of this multiplicity of definitions.)2010-12-29

3 Answers 3

13

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$.

  • 0
    @Michele Kakusi: That's not why Moron downvoted my answer. He downvoted it because (i) he edited it to make it wrong; (ii) I removed his edit, with a dismissive comment. (Just click on `edited Jan 3 at 22:04` to follow the edits.) I think the real reason for this spat is that Moron didn't pick up on the humour of "...or I will come and stalk you".2011-03-04
6

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.

  • 0
    Michele: the other rationale behind the definition that TonyK gave is that (with particular definitions) the adjacency matrix of the 'square' graph $G^2$ is precisely the (matrix-product) square of the adjacency matrix for the graph $G$ (including multiplicities - generally an edge is added from $u$ to $v$ for _each_ 2-path from $u$ to $v$ in $G$.)2011-01-03
1

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)$.

  • 0
    ...or, indeed, by treating undirected graphs simply as directed graphs where each edge goes both ways.2012-02-08