# Name of an operation on graphs

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.

• Note that the product of two 0-1 matrices is not necessarily a 0-1 matrix. Dec 6, 2010 at 14:50
• @J.M: That's okay. Positive integer entries correspond to more than one edge joining the appropriate vertices. Dec 6, 2010 at 14:58
• 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. Dec 6, 2010 at 15:26
• 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. Dec 6, 2010 at 16:53
• 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. Dec 6, 2010 at 16:54

Maybe it would be helpful... from position that $M$ is a hypergraph, value of matrix element $A_M(i,j)$ seems to be equal to the number of edges from vertex i to vertex j with length 2 (minus edges from j to i). But I'm not sure, if $A_M$ is adjacency matrix for hypergraph $M$... Especially after googling "hypergraph adjacency matrices"
As described in Brualdi and Cvetkovic's Combinatorial Approach to Matrix Theory, rather than associating a directed graph in the usual way to a matrix, it's more natural to associate the König digraph for the purposes of thinking about matrix multiplication. For an $m \times n$ non-negative integer matrix $A$, the König digraph is a bipartite digraph with vertex classes $X$ (with $n$ elements) and $Y$ (with $m$ elements) such that the number of edges from $x \in X$ to $y \in Y$ is $A_{yx}$. Composition of matrices then corresponds to "plugging" one digraph into another, and whatever purpose you want to multiply adjacency matrices for, I think it will be more natural (or at least equivalent) phrased in this language instead.
What I've described is a category whose objects are the non-negative integers $[n], n \ge 0$ and where a morphism from $[n]$ to $[m]$ is a collection of arrows from an $n$-element set to an $m$-element. This category is a certain refinement of the category of finite sets and relations and is a very natural setting for certain combinatorial arguments (as well as for, as the book says, a combinatorial approach to matrix theory). I don't know if it has a name, though.