Graph homomorphism
From Free net encyclopedia
In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. More concretely it maps adjacent vertices to adjacent vertices.
Contents |
Definition
A graph homomorphism <math>f</math> from a graph <math>G:=(V,E)</math> to a graph <math>G':=(V',E')</math>, written <math>f:G \rightarrow G'</math> is a mapping <math>f:V \rightarrow V'</math> from the vertex set of <math>G</math> to the vertex set of <math>G'</math> such that <math>\{f(u),f(v)\}\in E'</math> whenever <math>\{u,v\}\in E</math>.
The above definition is extended to directed graphs. Then, for a homomorphism <math>f:G \rightarrow G'</math>, <math>(f(u),f(v))</math> is an arc of <math>G'</math> if <math>(u,v)</math> is an arc of <math>G</math>.
If there exists a homomorphism <math>f:G\rightarrow H</math> we shall write <math>G\rightarrow H</math>, and <math>G\not\rightarrow H</math> otherwise. If <math>G\rightarrow H</math>, <math>G</math> is said to be homomorphic to <math>H</math> or <math>H</math>-colourable.
The composition of homomorphisms are homomorphisms. If the homomorphism <math>f:G\rightarrow G'</math> is a bijection whose inverse function is also a graph homomorphism, then <math>f</math> is a graph isomorphism. Determining whether there is an isomorphism between two graphs is an important problem in computational complexity theory; see graph isomorphism problem.
Two graphs <math>G</math> and <math>G'</math> are homomorphically equivalent if <math>G\rightarrow G'</math> and <math>G'\rightarrow G</math>.
A retract of a graph <math>G</math> is a subgraph <math>H</math> of <math>G</math> such that there exists a homomorphism <math>r:G\rightarrow H</math>, called retraction with <math>r(x)=x</math> for any vertex <math>x</math> of <math>H</math>. A core is a graph which does not retract to a proper subgraph. Any graph is homomorphically equivalent to a unique core.
Notes
- In terms of graph coloring, k-colourings of <math>G</math> are precisely homomorphisms <math>f:G\rightarrow K_k</math>. As a consequence if <math>G\rightarrow H</math>, the chromatic number of <math>G</math> is at most the one of <math>H</math>: <math>\chi(G)\leq\chi(H)</math>.
- Graph homomorphism preserves connectedness.
References
- P. Hell and J. Nesetril, Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and its Applications 28, Oxford University Press, 2004.