Relations between graphs

Given two graphs G = (VG,EG) and H = (V H,EH), we ask under which conditions there is a relation R VG × VH that generates the edges of H given the structure of the graph G. This construction can be seen as a form of multihomomorphism. It generalizes surjective homomorphisms of graphs and naturally leads to notions of R-retractions, Rcores, and R-cocores of graphs. Both R-cores and R-cocores of graphs are unique up to isomorphism and can be computed in polynomial time.