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 ?


One thought on “Question about graph homomorphism”

  1. That sounds right to me. Compare and contrast with a graph isomorphism, which has to be a bijection. The same issue seems to come up in lots of places: the book I’m reading on lattice theory led me last night to that same sort of distinction between homomorphisms and isomorphisms with various sorts of lattices, so I’d say the point you’ve noticed is valid.

Leave a Reply