Graph homomorphism

(Redirected from Graph isomorphism)

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

Contents

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$ .