Graph homomorphism
Encyclopedia : G : GR : GRA : Graph homomorphism
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.
Definition
A graph homomorphism [f] from a graph [G:=(V,E)] to a graph [G':=(V',E')], written [f:G \rightarrow G'] is a mapping [f:V \rightarrow V'] from the vertex set of [G] to the vertex set of [G'] such that [\\in E'] whenever [\\in E].
The above definition is extended to directed graphs. Then, for a homomorphism [f:G \rightarrow G'], [(f(u),f(v))] is an arc of [G'] if [(u,v)] is an arc of [G].
If there exists a homomorphism [f:G\rightarrow H] we shall write [G\rightarrow H], and [G\not\rightarrow H] otherwise. If [G\rightarrow H], [G] is said to be homomorphic to [H] or [H]-colourable.
The composition of homomorphisms are homomorphisms. If the homomorphism [f:G\rightarrow G'] is a bijection whose inverse function is also a graph homomorphism, then [f] 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 [G] and [G'] are homomorphically equivalent if [G\rightarrow G'] and [G'\rightarrow G].
A retract of a graph [G] is a subgraph [H] of [G] such that there exists a homomorphism [r:G\rightarrow H], called retraction with [r(x)=x] for any vertex [x] of [H]. 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 [G] are precisely homomorphisms [f:G\rightarrow K_k]. As a consequence if [G\rightarrow H], the chromatic number of [G] is at most the one of [H]: [\chi(G)\leq\chi(H)].
- 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.
See also
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.