Name of an operation on graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T07:37:28Z http://mathoverflow.net/feeds/question/49233 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/49233/name-of-an-operation-on-graphs Name of an operation on graphs Anthony Labarre 2010-12-13T09:15:46Z 2013-03-29T13:05:33Z <p>I asked this a week ago on <a href="http://math.stackexchange.com/questions/13244/name-of-an-operation-on-graphs" rel="nofollow">math.SE</a>, but haven't obtained an answer yet, so I hope it is fine to ask this here too.</p> <p>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)$.</p> <p>1) What is the name of the graph $M$ with adjacency matrix $A_M=A_HA_G$?</p> <p>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?</p> http://mathoverflow.net/questions/49233/name-of-an-operation-on-graphs/49260#49260 Answer by Todd Trimble for Name of an operation on graphs Todd Trimble 2010-12-13T14:14:44Z 2010-12-13T14:14:44Z <p>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)$. </p> <p>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 <a href="http://ncatlab.org/nlab/show/span" rel="nofollow">span</a>. In that case, $M$ would correspond to the span composite, as defined in the cited article. </p> <p>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). </p> <p>Please take this answer with a note of caution that I am not a graph theorist. </p> http://mathoverflow.net/questions/49233/name-of-an-operation-on-graphs/49322#49322 Answer by Martin Rubey for Name of an operation on graphs Martin Rubey 2010-12-13T22:35:49Z 2010-12-14T10:25:06Z <p>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$.</p> <p>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.</p> <p>Edit: maybe, to distinguish it from other products, call it "matrix product of graphs"?</p> http://mathoverflow.net/questions/49233/name-of-an-operation-on-graphs/125911#125911 Answer by AB Balbuena for Name of an operation on graphs AB Balbuena 2013-03-29T13:05:33Z 2013-03-29T13:05:33Z <p>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).</p>