Name of an operation on graphs - MathOverflow

Name of an operation on graphs

2010-12-13T09:15:46Z

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?

Answer by Todd Trimble for Name of an operation on graphs

2010-12-13T14:14:44Z

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.

Answer by Martin Rubey for Name of an operation on graphs

2010-12-13T22:35:49Z

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"?

Answer by AB Balbuena for Name of an operation on graphs

2013-03-29T13:05:33Z

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