0 KB487 KB75 KB200820252013Hubička, JanJost, JürgenLong, YangjingStadler, Peter F.Yang, Lingštevilka:2letnik:6str. 323-350COBISSID:16706393ISSN:1855-3966URN:URN:NBN:SI:doc-T7G62DNHenDruštvo matematikov, fizikov in astronomov SlovenijeArs mathematica contemporaneabinary relationcocoregeneralized surjective graph homomorphismmultihomomorphismR-coreR-reduced graphR-retractionteorija grafovRelations between graphs|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 \times 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 timeTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije