Premium
Homomorphism–homogeneous graphs
Author(s) -
Rusinov Momchil,
Schweitzer Pascal
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20478
Subject(s) - homomorphism , mathematics , combinatorics , homogeneous , graph homomorphism , cograph , monomorphism , discrete mathematics , morphism , graph , chordal graph , line graph , 1 planar graph , voltage graph , injective function
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–261, 2010