# Name of an operation on graphs

I asked this a week ago on math.SE, but haven't obtained an answer yet, so I hope it is fine to ask this here too.

Let $G$ and $H$ be two possibly directed, non necessarily simple, vertex-labelled graphs with respective adjacency matrices $A_G$ and $A_H$ and $V(G)=V(H)$.

1) What is the name of the graph $M$ with adjacency matrix $A_M=A_HA_G$?

2) Which symbols should I NOT use to denote it in order to avoid confusion with other graph products, in the event that none is already associated with this operation?

If you are disallowing multiple edges between vertices, then such graphs are the same things as binary relations $R$ on the vertex set (where $x R y$ iff there is an edge from $x$ to $y$. Then $M$ would correspond to the relational composite of $H$ and $G$: $x M z$ iff $\exists_y (x H y) \wedge (y G z)$.

If you are allowing multiple edges between vertices, so that adjacency matrices can have entries greater than 1, then such graphs are the same things as what category theorists are wont to call a span. In that case, $M$ would correspond to the span composite, as defined in the cited article.

Either way, it seems reasonable to call it the composite (unless that term is already used for some other operation on graphs), and to denote it by $H \circ G$ (under the same caveat).

Please take this answer with a note of caution that I am not a graph theorist.

In Spectra of graphs: theory and application, Dragoš M. Cvetković, Michael Doob, Horst Sachs, pg. 52, Section 2.1 "The polynomial of a Graph", it's called product and denoted $G_1\cdot G_2$.

I would hesitate to call it composition, lest it is confused with the lexicographic product, which is, however, denoted $G_1[G_2]$ in the reference above.

Edit: maybe, to distinguish it from other products, call it "matrix product of graphs"?

• Thanks for the reference. I'm a bit reluctant to use the word "product", because of the many different uses for that term -- and the symbol's already taken too. However, what you quote seems most natural to me. I presume it wouldn't hurt to use that in a paper, as long as everything is stated and defined well enough to avoid confusion. Dec 13, 2010 at 22:52
• @Martin are you sure? This operation seems to be defined only for two graphs $G$ and $H$ with the same vertex set. If one thinks of $G$ as having red edges and $H$ as having blue then it could be called the $"red-blue paths graph$ since each edge from $u$ to $v$ represents a path $uwv$ of that sort. Dec 14, 2010 at 7:01
• Yes, I'm sure that in this section of the reference it's called "the product", and the union is called the union (sic!). The section is only 2 and a half pages, and is mostly concerned with the graph polynomial, where the problem of different vertex sets does not occur. Dec 14, 2010 at 9:37

I just came across the article titled Matrix Product of Graphs'' (http://link.springer.com/chapter/10.1007%2F978-81-322-1053-5_4) which may answer your first question (or may have been motivated by your question).

• Thanks, I hope to be able to read that soon (Springer does not allow me to). Apr 5, 2013 at 10:33
• @AnthonyLabarre Ah, so sad I didn't come across this question and this comment sooner. Did you manage to find the paper? You can find a pre-print here: researchgate.net/publication/235980603_Matrix_Product_of_Graphs Mar 23, 2016 at 7:04
• Briefly, the paper investigates exactly when the (usual matrix) product of two (simple, undirected) graph adjacency matrices is again the adjacency matrix of some graph (i.e., is a symmetric, zero diagonal, 0-1 matrix). Mar 23, 2016 at 7:07
• @M.Vinay Yes, I was able to find the paper, thanks anyway for the link. Mar 23, 2016 at 19:10
• @AnthonyLabarre Happy to hear that. Mar 23, 2016 at 19:11