# 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\leq|i(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 one-to-one (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 well-defined 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 non-isomorphic 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 2013-03-22 16:04:53 Last modified on 2013-03-22 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