Relations between graphs - Hubička, Jan (Ars mathematica contemporanea, 2013)
Given two graphs ?$G = (V_G, E_G)$? and ?$H = (V_H, E_H)$?, we ask under which conditions there is a relation ?$R \subseteq V_G × V_H$? 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, ?$R$?-cores, 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.
Keywords: binary relation; cocore; generalized surjective graph homomorphism; multihomomorphism; R-core; R-reduced graph; R-retraction; teorija grafov