Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Trying to systematize possible notions of graph morphisms I came about the following classification:

A morphism $f$ which sends a graph $G$ to another graph $G'$ is – first of all – supposed to be a function $f:V_G\rightarrow V_{G'}$ from the vertex-set of $G$ to the vertex-set of $G'$, that has to fulfill one or more conditions of the form

$$\phi(x,y) \rightarrow \phi(x',y')$$

or of the form

$$\phi(x',y') \rightarrow \phi(x,y)$$

Here $\phi(\cdot,\cdot)$ is either

  • $\cdot = \cdot$
  • $R(\cdot,\cdot)$, that means "$\cdot$ is related to $\cdot$",
  • a negation of one of the former
  • or any formula with two free variables of the first-order language with signature $\lbrace R, = \rbrace$ (called appropriate formula)

$\phi(x,y) \rightarrow \phi(x',y')$ is to be read

$$(\forall x,y \in V_G)\ \phi(x,y) \rightarrow \phi(f(x),f(y))$$

which is equivalent to

$$(\forall x,y \in V_{G})\ \phi(x,y)\rightarrow (\exists x',y' \in V_{G'})\ \phi(x',y') \wedge f(x)=x' \wedge f(y)=y'$$

$\phi(x',y') \rightarrow \phi(x,y)$ instead is to be read

$$(\forall x',y' \in V_{G'})\ \phi(x',y')\rightarrow (\exists x,y \in V_G)\ \phi(x,y) \wedge f(x)=x' \wedge f(y)=y'$$

Now look at the following specific restrictions:

  1. $x\neq y \rightarrow x' \neq y'$ ($f$ is injective)
  2. $x'=y' \rightarrow x = y$ ($f$ is surjective)
  3. $R(x,y) \rightarrow R(x',y')$ ($f$ is a weak homomorphism)
  4. $R(x',y') \rightarrow R(x,y)$ ($f$ is a strong homomorphism)
  5. $x=y \rightarrow x' = y'$ ($f$ is a function)
  6. $x'\neq y' \rightarrow x \neq y$ ($f$ is bijective)

The last two conditions seem to be unnecessary, i.e. definable.

Combinations of the other ones yield:

  • embeddings: strong + injective

  • elementary embeddings: for every appropriate formula $\phi$

$$\phi(x,y) \rightarrow \phi(x',y')$$

which implies for every appropriate formula $\phi$

$$\phi(x',y') \rightarrow \phi(x,y)$$

I would like to learn to what extent this classification is complete.

share|cite|improve this question
up vote 0 down vote accepted

First of all, this classification can be done for any first order language and is not special to graphs. I think your interpretation of $\phi(x', y') \to \phi(x, y)$ is a bit unnatural since it implies the existence of preimage whenever $\phi(x', y')$ holds.

You can do the classification like this. First, you deal only with functions. The function can of course be injective, surjective, or bijective. Then you can look for “structure preservation”. We'll say that $f$ preserves the operation $O$ of arity $n$ if $f(O(x_1, … x_n)) = O(f(x_1), … f(x_n))$. And $f$ preserves the relation $R$ of arity $n$ if $R(x_1, …, x_n) \implies R(f(x_1), …, f(x_n))$. That's your condition 3. And $f$ reflects the relation $R$ if $R(f(x_1), …, f(x_n)) \implies R(x_1, …, x_n)$. That's like your condition 4. but does not force you to have preimages of related elements of the codomain. Also note that there is no difference between preservation and reflection of an operation (and that's why homomorphisms of algebraic structures ale always strong, so bijective homomorphism is an isomorphism).

A function between two first order structures of the same type is a homomorphism if it preserves all operations and relations. And it's a strong homomorphism if it also reflects the relations (your condition 4. doesn't imply preservation of R). It's an embedding if it's injection and strong homomorphism and isomorphism if it's bijective and strong homomorphism (that's equivalent to categorical notion of isomorphism since its inverse exists). Yes, and elementary embedding mean injection which preserves all parametric formulas (which implies being homomorphism if = is in the language). Also you can say endomorphism for homomorphism when domain and codomain is the same and automorphism for isomorphism in that case. Sometimes injective homomorphism can be called monomorphism and surjective homomorphism can be call epimorphism, but these notions differ from categorical ones in general.

share|cite|improve this answer
I found the seemingly unnatural notion of $\phi(x',y') \rightarrow \phi(x,y)$ in the definition of strong homomorphism at Wikipedia:… – Hans Stricker Jul 30 '13 at 11:05
I see. It's a different definition of strong homomorphism than I know. However even in Wiki definition $\phi(x', y') \rightarrow \phi(x, y)$ is a condition for being a strong homomorphism in addition to being homomorphism. So $\phi(x, y) \leftrightarrow \phi(x, y)$ would be better for strong homomorphism in your notation. – user87690 Aug 2 '13 at 18:50
@HansStricker Note my related question…. – user87690 Aug 15 '13 at 7:11

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.