Abstract | ||
---|---|---|
Given two graphs G = (V-G,V- E-G) and H = (V-H, E-H), we ask under which conditions there is a relation R subset of V-G x 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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.26493/1855-3974.335.d57 | ARS MATHEMATICA CONTEMPORANEA |
Keywords | Field | DocType |
Generalized surjective graph homomorphism,R-reduced graph,R-retraction,binary relation,multihomomorphism,R-core,cocore | Topology,Discrete mathematics,Combinatorics,Indifference graph,Graph isomorphism,Graph homomorphism,Chordal graph,Graph product,Symmetric graph,Pathwidth,1-planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
6 | 2 | 1855-3966 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jan Hubicka | 1 | 55 | 12.83 |
Jürgen Jost | 2 | 95 | 12.39 |
Yangjing Long | 3 | 0 | 1.01 |
Peter F. Stadler | 4 | 1839 | 152.96 |
Ling Yang | 5 | 0 | 0.34 |