A homomorphism from one graph to another is a map that sends vertices to vertices and edges to edges. We denote the number of homomorphisms from G to H by |G → H|. If 𝓕 is a collection of graphs, we say that 𝓕 distinguishes graphs G and H if there is some member X of 𝓕 such that |G → X | ≠ |H → X|. 𝓕 is a distinguishing family if it distinguishes all pairs of graphs. We show that various collections of graphs are a distinguishing family.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1008,
author = {Steve Fisk},
title = {Distinguishing graphs by the number of homomorphisms},
journal = {Discussiones Mathematicae Graph Theory},
volume = {15},
year = {1995},
pages = {73-75},
zbl = {0833.05029},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1008}
}
Steve Fisk. Distinguishing graphs by the number of homomorphisms. Discussiones Mathematicae Graph Theory, Tome 15 (1995) pp. 73-75. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1008/
[000] [Lov71] L. Lovász, On the cancellation law among finite relational structures, Periodica Math. Hung. 1 (1971) 145-156, doi: 10.1007/BF02029172. | Zbl 0223.08002