4
$\begingroup$

There is a whole bunch of definitions of graph products, but only one of them - the tensor product - is the categorical product in the (standard) category of graphs with graph homomorphisms.

I'd like to know whether there are other graph categories - with other morphisms than homomorphims - with respect to which one or the other of the other graph products are categorical products.

2 Answers 2

4

The lexicographical and rooted product cannot be a categorical product, since that should be commutative (up to isomorphism).

For the rest, try to define morphisms as themselves some (kind of bipartite) graphs. I'm not sure yet if we can achieve them all..

5

There is a good treatment of this question in "Algebraic Graph Theory" by Ulrich Knauer.

If you look at weak graph homomorphisms, which he calls egamorphisms, then the product in that category is what he calls the boxcross product (A weak homomorphism allows edges to be mapped to vertices as long as their endpoints are approppriately mapped). It is like the categorial product in the normal category with the addition of edges from to for every a, and conversely for fixed b. Another way to view this is to notice that the category of graphs under egamorphisms is the same as the category of reflexive graph under reflexive graph homomorphisms.

If instead you have continuous homomorphisms, so edges between the images of two vertices must themselves have a pre-image, then you get another category of graphs wherein the disjunction is now the categorial product.

These are the only 3 instances of which I am familiar where this occurs. Knauer also considers a number of other kinds of homomorphisms and shows how the resulting categories do not have products. For more detail I strongly suggest Chapter 4 of the book.