Relations between graphs

Jan Hubička, Jürgen Jost, Yangjing Long, Peter F. Stadler, Ling Yang


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.


Generalized surjective graph homomorphism, R-reduced graph, R-retraction, binary relation, multihomomorphism, R-core, cocore

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications