You are here
Homegraph homomorphism
Primary tabs
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\leqi(e)\leq 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
$\displaystyle 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}\Longrightarrow\{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,
$\xymatrix{a\ar[r]&b\ar[d]\\ c\ar[u]&d\ar[l]}\qquad\qquad\qquad\qquad\xymatrix{r\ar[r]&s\\ t\ar[u]\ar[r]&u\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.
Mathematics Subject Classification
05C75 no label found05C60 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections