Publications - Published papers
Please find below publications of our group. Currently, we list 565 papers. Some of the publications are in collaboration with the group of Sonja Prohaska and are also listed in the publication list for her individual group. Access to published papers (
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:©NOTICE: All papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.
Relations Between Graphs
Jan Hubička, Jürgen Jost, Yangjing Long and Peter F. Stadler
Download
Status: Published
Ars Math Contemp 6: 323-350 (2013)
Abstract
Given two graphs <i>G=(V<sub>G</sub>,E<sub>G</sub>)</i> and <i>H=(V_H,E_H)</i>, we ask under which conditions there is a relation <i>R ⊆ V<sub>G</sub>×V<sub>H</sub> that generates
the edges of <i>H</i> given the structure of the graph <i>G</i>. 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
generalized surjective graph homomorphism, R-reduced graph, R-retraction, binary relation, multihomomorphism, R-core, cocore