graph homomorphism

In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. More concretely it maps

vertices to vertices
undirected edges to undirected edges or collapses the edge onto a vertex.
directed edges to directed edges (without changing direction) or collapses the edge onto a vertex

Definition

A graph homomorphism

f

from a graph

G:=(V,E)

to a graph

G':=(V',E')

is a function

f:V \cup E \to V' \cup E'

on the edges and vertices of

G

such that

vertices of $G$ go to vertices of $G'$ ,
if $e$ is an edge of $G$ with endpoints $v$ and $w$ then either $f(e)$ is an edge of $G'$ with endpoints $f(v)$ and $f(w)$ , or $f(e)=f(v)=f(w)$ , and
if $e$ is a directed edge of $G$ from $v$ to $w$ then either $f(e)$ is a directed edge of $H$ from $f(v)$ to $f(w)$ , or $f(e)=f(v)=f(w)$ .

The above definition works even when

G

and

G'

are allowed to have multiedges and loops. In the case of simple graphs, the definition can is slightly simpler: where an edge maps is determined by where its endpoints map. Some authors use a stricter definition than the one given here, in which an edge is not allowed to map to a vertex. Thus, if the destination graph has no loops, adjacent vertices can't map to the same vertex. If the homomorphism

f

is a bijection, then the inverse function is also a graph homomorphism, so

f

is a graph isomorphism. In this case, the two graphs are identical from the viewpoint of graph theory.

Examples

The function

f:G \to K_1

mapping a graph

G

to the complete graph with one vertex is a graph homomorphism.

Notes

In terms of graph coloring, a k-coloring of G, without restrictions, is equivalent to a homomorphism of G into K_k, the complete graph on k vertices. (Each vertex of

G

is colored according to which vertex of

K_k

it goes to.) As an extension of that analogy, a homomorphism of G into H is also sometimes called an H-coloring.

Properties

Graph homomorphism preserve connectedness and diconnectedness.

A graph H is a subgraph of G if and only if there exists a monomorphism $f:H\to G$ .