Name
Abstract | ||
|---|---|---|
We answer two open questions posed by Cameron and Nesetril concerning homomorphism–homogeneous graphs. In particular we show, by giving a characterization of these graphs, that extendability to monomorphism or to homomorphism leads to the same class of graphs when defining homomorphism–homogeneity. Further, we show that there are homomorphism–homogeneous graphs that do not contain the Rado graph as a spanning subgraph answering the second open question. We also treat the case of homomorphism–homogeneous graphs with loops allowed, showing that the corresponding decision problem is co–NP complete. Finally, we extend the list of considered morphism–types and show that the graphs for which monomorphisms can be extended to epimor-phisms are complements of homomorphism–homogeneous graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 65:253–262, 2010 © 2010 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1002/jgt.20478 | Journal of Graph Theory |
Keywords | Field | DocType |
homogeneous graph,wiley periodicals,inc. j graph theory,open question,defining homomorphism,corresponding decision problem,rado graph,homogeneity,graphs,homomorphisms | Discrete mathematics,Indifference graph,Combinatorics,Clique-sum,Chordal graph,Cograph,Graph product,Pathwidth,Universal graph,Mathematics,Split graph | Journal |
Volume | Issue | Citations |
65 | 3 | 7 |
PageRank | References | Authors |
0.81 | 5 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Momchil Rusinov | 1 | 7 | 0.81 |
| Pascal Schweitzer | 2 | 214 | 16.94 |