Hubicka, JanJanHubickaJost, JürgenJürgenJostLong, YangjingYangjingLongStadler, Peter F.Peter F.StadlerYang, LingLingYang2022-03-042022-03-042013https://publica.fraunhofer.de/handle/publica/233050Given 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.engeneralized surjective graph homomorphismR-reduced graphR-retractionbinary relationmultihomomorphismR-corecocore610journal article