Graph homomorphism

From Wikipedia, the free encyclopedia

Not to be confused with graph homeomorphism.

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.

1 Definition
2 Notes
3 References
4 See also

[edit] 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 $\{f(u),f(v)\}\in E'$ whenever $\{u,v\}\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.

[edit] Notes

In terms of graph coloring, k-colourings of $G$ are precisely homomorphisms $f:G\rightarrow K_k$ , where $K k$ is the complete graph with $k$ nodes. As a consequence if $G\rightarrow H$ , the chromatic number of $G$ is at most the one of $H$ : χ(G) ≤ χ(H).
if $G\rightarrow H$ , the odd girth of $G$ is at least the one of $H$ .
Graph homomorphism preserves connectedness.
The tensor product of graphs is the category-theoretic product for the category of graphs and graph homomorphisms.
The associated decision problem, i.e. deciding whether there exists a homomorphism from one graph to another, is NP-complete.

[edit] References

Hell, Pavol; Jaroslav Nešetřil (2004). Graphs and Homomorphisms (Oxford Lecture Series in Mathematics and Its Applications). Oxford University Press. ISBN 0-19-852817-5.