graph homomorphism
We shall define what a graph homomorphism is between two pseudographs^{}, so that a graph homomorphism between two multigraphs^{}, or two graphs are special cases.
Recall that a pseudograph $G$ is an ordered triple $(V,E,i)$, where $V$ is a set called the vertex set of $G$, $E$ is a set called the edge set of $G$, and $i:E\to {2}^{V}$ is a map (incidence map), such that for every $e\in E$, $1\le i(e)\le 2$.
Elements of $V$ are called vertices, elements of $E$ edges. The vertex/vertices associated with any edge $e$ via the map $i$ is/are called the endpoint^{}(s) of $e$. If an edge $e$ has only one endpoint, it is called a loop. ${e}_{1}$ and ${e}_{2}$ are said to be parallel^{} if $i({e}_{1})=i({e}_{2})$.
As two examples, a multigraph is a pseudograph such that $i(e)=2$ for each edge $e\in E$ (no loops allowed). A graph is a multigraph such that $i$ is onetoone (no parallel edges allowed).
Definition. Given two pseudographs ${G}_{1}=({V}_{1},{E}_{1},{i}_{1})$ and ${G}_{2}=({V}_{2},{E}_{2},{i}_{2})$, a graph homomorphism $h$ from ${G}_{1}$ to ${G}_{2}$ consists of two functions $f:{V}_{1}\to {V}_{2}$ and $g:{E}_{1}\to {E}_{2}$, such that
${i}_{2}\circ g={f}^{*}\circ {i}_{1}.$  (1) 
The function ${f}^{*}:{2}^{{V}_{1}}\to {2}^{{V}_{2}}$ is defined as ${f}^{*}(S)=\{f(s)\mid s\in S\}$.
A graph isomorphism^{} $h=(f,g)$ is a graph homomorphism such that both $f$ and $g$ are bijections^{}. It is a graph automorphism if ${G}_{1}={G}_{2}$.
Remarks.

•
In case when ${G}_{1}$ and ${G}_{2}$ are graphs, a graph homomorphism may be defined in terms of a single function $f:{V}_{1}\to {V}_{2}$ satisfying the condition (*)
$\{{v}_{1},{v}_{2}\}$ is an edge of ${G}_{1}\u27f9\{f({v}_{1}),f({v}_{2})\}$ is an edge of ${G}_{2}$.
To see this, suppose $h=(f,g)$ is a graph homomorphism from ${G}_{1}$ to ${G}_{2}$. Then ${f}^{*}{i}_{1}(e)={f}^{*}(\{{v}_{1},{v}_{2}\})=\{f({v}_{1}),f({v}_{2})\}={i}_{2}(g(e))$. The last equation says that $f({v}_{1})$ and $f({v}_{2})$ are endpoints of $g(e)$. Conversely, suppose $f:{V}_{1}\to {V}_{2}$ is a function sastisfying condition (*). For each $e\in {E}_{1}$ with end points $\{{v}_{1},{v}_{2}\}$, let ${e}^{\prime}\in {E}_{2}$ be the edge whose endpoints are $\{f({v}_{1}),f({v}_{2})\}$. There is only one such edge because ${G}_{2}$ is a graph, having no parallel edges. Define $g:{E}_{1}\to {E}_{2}$ by $g(e)={e}^{\prime}$. Then $g$ is a welldefined function which also satisfies Equation (1). So $h:=(f,g)$ is a graph homomorphism ${G}_{1}\to {G}_{2}$.

•
The definition of a graph homomorphism between pseudographs can be analogously applied to one between directed pseudographs. Since the incidence map $i$ now maps each edge to an ordered pair of vertices, a graph homomorphism thus defined will respect the “direction” of each edge. For example,
$$\text{xymatrix}a\text{ar}[r]\mathrm{\&}b\text{ar}[d]c\text{ar}[u]\mathrm{\&}d\text{ar}[l]\mathit{\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}}\text{xymatrix}r\text{ar}[r]\mathrm{\&}st\text{ar}[u]\text{ar}[r]\mathrm{\&}u\text{ar}[u]$$ are two nonisomorphic digraphs^{} whose underlying graphs are isomorphic. Note that one digraph is strongly connected^{}, while the other is only weakly connected.
Title  graph homomorphism 
Canonical name  GraphHomomorphism 
Date of creation  20130322 16:04:53 
Last modified on  20130322 16:04:53 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  11 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 05C75 
Classification  msc 05C60 
Synonym  graph automorphism 
Related topic  GraphIsomorphism 
Related topic  Pseudograph 
Related topic  Multigraph 
Related topic  Graph 