Graph homomorphism

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

Definitions

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 $\{u,v\}\in E$ implies $\{f(u),f(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.

If the homomorphism $f:G\rightarrow G'$ is a bijection whose inverse function is also a graph homomorphism, then f is a graph isomorphism.

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.

Properties

The composition of homomorphisms are homomorphisms.

Graph homomorphism preserves connectedness.

The tensor product of graphs is the category-theoretic product for the category of graphs and graph homomorphisms.

Connection to coloring and girth

A graph coloring is an assignment of one of k colors to a graph G so that the endpoints of each edge have different colors, for some number k. Any coloring corresponds to a homomorphism $f:G\rightarrow K_k$ from G to a complete graph Kk: the vertices of Kk correspond to the colors of G, and f maps each vertex of G with color c to the vertex of Kk that corresponds to c. This is a valid homomorphism because the endpoints of each edge of G are mapped to distinct vertices of Kk, and every two distinct vertices of Kk are connected by an edge, so every edge in G is mapped to an adjacent pair of vertices in Kk. Conversely if f is a homomorphism from G to Kk, then one can color G by using the same color for two vertices in G whenever they are both mapped to the same vertex in Kk. Because Kk has no edges that connect a vertex to itself, it is not possible for two adjacent vertices in G to both be mapped to the same vertex in Kk, so this gives a valid coloring. That is, G has a k-coloring if and only if it has a homomorphism to Kk.

If there are two homomorphisms $H\rightarrow G\rightarrow K_k$, then their composition $H\rightarrow K_k$ is also a homomorphism. In other words, if a graph G can be colored with k colors, and there is a homomorphism $H\rightarrow G$, then H can also be k-colored. Therefore, whenever a homomorphism $H\rightarrow G$ exists, the chromatic number of H is less than or equal to the chromatic number of G.

Homomorphisms can also be used very similarly to characterize the girth of a graph G, the length of its shortest cycle, and the odd girth, the length of the shortest odd cycle. The girth is, equivalently, the smallest number g such that a cycle graph Cg has a homomorphism $C_g\rightarrow G$, and the odd girth is the smallest odd number g for which there exists a homomorphism $C_g\rightarrow G$. For this reason, if $G\rightarrow H$, then the girth and odd girth of G are both greater than or equal to the corresponding invariants of H.

Complexity

The associated decision problem, i.e. deciding whether there exists a homomorphism from one graph to another, is NP-complete. Determining whether there is an isomorphism between two graphs is also an important problem in computational complexity theory; see graph isomorphism problem.

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.

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Homomorphism — In abstract algebra, a homomorphism is a structure preserving map between two algebraic structures (such as groups, rings, or vector spaces). The word homomorphism comes from the Greek language: ὁμός (homos) meaning same and μορφή (morphe)… …   Wikipedia

• Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

• Graph isomorphism — In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly… …   Wikipedia

• Graph of groups — In geometric group theory, a graph of groups is an object consisting of a collection of groups indexed by the vertices and edges of a graph, together with a family of injective homomorphisms of the edge groups into the vertex groups.There is a… …   Wikipedia

• Induced homomorphism — In mathematics, an induced homomorphism is a structure preserving map between a pair of objects that is derived in a canonical way from another map between another pair of objects. A particularly important case arises in algebraic topology, where …   Wikipedia

• Conceptual graph — Conceptual graphs (CGs) are a formalism for knowledge representation. In the first published paper on CGs, John F. Sowa (Sowa 1976) used them to represent the conceptual schemas used in database systems. The first book on CGs (Sowa 1984) applied… …   Wikipedia

• Median graph — The median of three vertices in a median graph In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest… …   Wikipedia

• List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

• Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia

• Core (graph theory) — This article is about graph homomorphisms. For the subgraph in which all vertices have high degree, see k core. In the mathematical field of graph theory, a core is a notion that describes behavior of a graph with respect to graph homomorphisms.… …   Wikipedia