Relations between graphs
Keywords:Generalized surjective graph homomorphism, R-reduced graph, R-retraction, binary relation, multihomomorphism, R-core, cocore
Given two graphs G = (VG, EG) and H = (VH, 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, 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.
Articles in this journal are published under Creative Commons Attribution 4.0 International License