Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
Note that the product of two 0-1 matrices is not necessarily a 0-1 matrix. –  Guess who it is. Dec 6 '10 at 14:50
@J.M: That's okay. Positive integer entries correspond to more than one edge joining the appropriate vertices. –  Grumpy Parsnip Dec 6 '10 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. –  Anthony Labarre Dec 6 '10 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. –  Qiaochu Yuan Dec 6 '10 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. –  Ross Millikan Dec 6 '10 at 16:54

3 Answers 3

I believe this is known as Graph Squaring. See also here.

share|improve this answer
No, it's not. When you take powers of graphs you ignore the multiplicity of the edges. The formula given in the article is wrong. –  Qiaochu Yuan Dec 6 '10 at 16:51

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"

share|improve this answer

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.