3
$\begingroup$

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) In the unlikely event that I am the first to think about using that operation, which symbols should I NOT use to denote it in order to avoid confusion with other graph products?

UPDATE: I have now asked this question on MathOverflow as well.

  • 1
    Note that the product of two 0-1 matrices is not necessarily a 0-1 matrix.2010-12-06
  • 0
    @J.M: That's okay. Positive integer entries correspond to more than one edge joining the appropriate vertices.2010-12-06
  • 0
    J. M. is indeed right, and I'll have to choose my graphs carefully. However, I don't think it affects my question, as Jim Conant points out.2010-12-06
  • 1
    You are certainly not the first to think about using this operation, in the sense that it is a natural operation and will surely occur to anyone who takes adjacency matrices seriously (for example I have used it in certain combinatorial proofs). But if it has a name, I don't know that you'll find it in the graph theory literature, since most graph theorists don't seem to care about directed graphs with more than one edge between vertices.2010-12-06
  • 1
    You better have the same number of vertices in G and H for the product to be defined. If they are on the same vertices and you make the matrix not (0,1) but reflecting the number of edges between vertices, then I think the product matrix will be the number of paths from a vertex to another that start with a step in G and then have a step in H.2010-12-06

3 Answers 3