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
- 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
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 Kk, the complete graph on k vertices. (Each vertex of G is colored according to which vertex of Kk it goes to.) As an extension of that analogy, a homomorphism of G into H is also sometimes called an H-coloring.
Properties
See also