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.

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.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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..

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.