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