Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
This might mean cartesian product? Which of course doesn't yield another graph, so the answer depends a lot on the context... –  Aaron Mazel-Gee Dec 26 '10 at 19:49
    
@Aaron: there is a standard definition of the Cartesian product of two graphs: en.wikipedia.org/wiki/Cartesian_product_of_graphs . Oddly enough it is not the categorical product. –  Qiaochu Yuan Dec 26 '10 at 20:51
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.) –  Pete L. Clark Dec 29 '10 at 7:33
add comment

3 Answers 3

up vote 11 down vote accepted

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

share|improve this answer
3  
Here is a book which has this definition: 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). –  Aryabhata Dec 26 '10 at 19:58
1  
Another reference: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.6167 –  Qiaochu Yuan Dec 26 '10 at 20:50
    
You should probably say, rather, one square of a graph is... –  Mariano Suárez-Alvarez Jan 3 '11 at 16:06
3  
@Moron: 1. Because I started with the graph G. So I don't want to add edges that are already there. 2. Because it's "at most", not "atmost". Now remove your downvote, or I will come and stalk you. –  TonyK Jan 3 '11 at 17:34
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 :-) –  TonyK Jan 3 '11 at 21:23
show 6 more comments

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.

share|improve this answer
    
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. –  Aryabhata Dec 26 '10 at 20:21
    
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. –  Qiaochu Yuan Dec 26 '10 at 20:53
    
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? –  Michele Kakusi Dec 27 '10 at 1:17
    
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$.) –  Steven Stadnicki Jan 3 '11 at 18:37
add comment

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

share|improve this answer
    
...or, indeed, by treating undirected graphs simply as directed graphs where each edge goes both ways. –  Ilmari Karonen Feb 8 '12 at 20:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.