# Systematizing graph morphisms

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.

-

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).
I found the seemingly unnatural notion of $\phi(x',y') \rightarrow \phi(x,y)$ in the definition of strong homomorphism at Wikipedia: en.wikipedia.org/wiki/… – 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