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.

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

3 Answers 3

1
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 6, 2010 at 16:51
1
$\begingroup$

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"

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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