4
$\begingroup$

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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Anthony Labarre
    Commented Dec 13, 2010 at 22:52
  • $\begingroup$ @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. $\endgroup$
    – Aaron Meyerowitz
    Commented Dec 14, 2010 at 7:01
  • $\begingroup$ 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. $\endgroup$
    – Martin Rubey
    Commented Dec 14, 2010 at 9:37
2
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Thanks, I hope to be able to read that soon (Springer does not allow me to). $\endgroup$
    – Anthony Labarre
    Commented Apr 5, 2013 at 10:33
  • $\begingroup$ @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 $\endgroup$
    – M. Vinay
    Commented Mar 23, 2016 at 7:04
  • $\begingroup$ 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). $\endgroup$
    – M. Vinay
    Commented Mar 23, 2016 at 7:07
  • 1
    $\begingroup$ @M.Vinay Yes, I was able to find the paper, thanks anyway for the link. $\endgroup$
    – Anthony Labarre
    Commented Mar 23, 2016 at 19:10
  • $\begingroup$ @AnthonyLabarre Happy to hear that. $\endgroup$
    – M. Vinay
    Commented Mar 23, 2016 at 19:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .