Graph isomorphism - Definition and Overview

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 <math>f<math> from a graph <math>G:=(V,E)<math> to a graph <math>G':=(V',E')<math> is a function

on the edges and vertices of <math>G<math> such that

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

The above definition works even when <math>G<math> and <math>G'<math> 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 <math>f<math> is a bijection, then the inverse function is also a graph homomorphism, so <math>f<math> is a graph isomorphism. In this case, the two graphs are identical from the viewpoint of graph theory.

Examples

The function

mapping a graph <math>G<math> 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 <math>G<math> is colored according to which vertex of <math>K_k<math> it goes to.) As an extension of that analogy, a homomorphism of G into H is also sometimes called an H-coloring.

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