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

on the edges and vertices of G such that

1. vertices of G go to vertices of G',
2. 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
3. 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

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 .

See also

• Graph rewriting