A morphism between graphs is required to preserve structure, so,
A morpism between preordered sets is:
where:

So a morphism between graphs maps nodes to nodes and edges to edges in a way the preserves the structure.
Decision Problem
Deciding if there is a morphism between graphs is an NPcomplete problem. That is:
 It can be done in polynomial time.
 but there is no known efficient way to locate a solution.
Deciding if there is an isomorphism between graphs is also an important problem in computational complexity theory.
Hom Sets
We will use the notation:
Hom(A,X)
to denote all the possible morphisms from graph 'A' to graph 'X'.
Properties of Morphisms of Graphs
 If the output of one graphmorphism is the input to another graphmorphism then the morphisms can be composed to form another morphism.
 Graph morphism preserves connectedness.
 The tensor product of graphs is the categorytheoretic product for the category of graphs and graph morphisms.
Graph Colourings
Graph colourings are an example of a graphmorphism where each node maps to a given colour.
Endomorphisms on Graphs