Tag Archives: homomorphism

Question about graph homomorphism

According to the definition:

A graph (V, A, src, tgt) involves two sets and two functions. For two graphs to be comparable, their two sets and their two functions should be appropriately comparable. Let G = (V, A, src, tgt) and G′ = (V′, A′, src′, tgt′) be graphs. A graph homomorphism f from G to G′, denoted f : GG′, consists of two functions f0: VV′ and f1: AA′ …the rest…

So this means that not all elements of A’ need to have a mapping from A and not all elements of V’ need to have a mapping from V. For example if G has m vertices and n edges and G’ has m'(>1) vertices and n'(>1) edges we could have all vertices of G go to one vertex of G'(say a) and all edges of G go to an edge from a to a(assuming that exists) in G’. That would be a valid homomorphism. Am I understanding that correctly ?