7
$\begingroup$

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

  • 3
    This might mean cartesian product? Which of course doesn't yield another graph, so the answer depends a lot on the context...2010-12-26
  • 0
    @Aaron: there is a standard definition of the Cartesian product of two graphs: http://en.wikipedia.org/wiki/Cartesian_product_of_graphs . Oddly enough it is not the categorical product.2010-12-26
  • 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$.

  • 3
    Here is a book which has this definition: http://books.google.com/books?id=AnqFawQJVm0C&pg=PA218 (See first paragraph of 10.3). Even Frank Harary's book on graph theory has this definition, but I was not able to find an online reference. btw, distance is _atmost_ 2 (I edited it for you).2010-12-26
  • 1
    Another reference: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.61672010-12-26
  • 0
    You should probably say, rather, *one square of a graph is...*2011-01-03
  • 0
    @Tony. Why did you remove the _atmost_? -1.2011-01-03
  • 0
    @Tony: Err right. My mistake. I missed that you are _adding_ new edges. You get your upvote back :-) I am free to downvote how I think is appropriate (however inappropriate that might be) though. Don't tell me how to vote.2011-01-03
  • 0
    @Moron: I didn't tell you how to vote until after you'd *ruined my answer*! So don't get shirty with me sonny.2011-01-03
  • 0
    @Tony: I could have downvoted the answer for having provided no references to backup your definition, instead of providing them for you (and upvoting). I was only trying to help. So what if I misread (twice!)? Don't be such a Jerk. Anyway, my apologies if I caused you some distress.2011-01-03
  • 1
    @Moron: "Don't be such a Jerk. Anyway, my apologies if I caused you some distress." A nice juxtaposition. An oxyMoron, if you will :-)2011-01-03
  • 0
    Hi Moron, I am relatively new to this, but it seems to me inappropriate to downvote an answer because they did not include a reference. I can see how you might not upvote it because of that (even if I do not agree with it), but downvoting it means that you are saying: "making a little effort, but not as much as I want (you to make) deserves punishment". In other words, I for one appreciate if someone is taking the trouble to answer but not wanting to spend the time to dig up a reference. If they do it from the kindness of their heart, great, but I cannot expect them to do that.2011-02-15
  • 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
    Do you have a reference which has this definition? Most of the definitions of the square of a graph I have come across agree with TonyK's answer.2010-12-26
  • 0
    The names I know for these notions are Cartesian and tensor product; I agree that box product is probably a better name for the first notion. But I don't think that this is what most people who use the phrase "the square of a graph" mean.2010-12-26
  • 0
    Davis, this is certainly interesting. I suppose one rationale I could think of for the definition TonyK gave (and thanks to Moron for the reference, which makes it reasonable to believe that this is the usual terminology) is that if you think of a graph as a category, so the edges represent maps, then $G^2=G\circ G$ could stand for the composition of those maps. I guess this would actually suggest to make edges for those points that are connected by a path of length $2$ exactly. Then again, what do *I* know?2010-12-27
  • 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