PDF

Discussiones Mathematicae Graph Theory  15(1) (1995)   73-75
DOI: https://doi.org/10.7151/dmgt.1008

DISTINGUISHING GRAPHS BY THE NUMBER OF HOMOMORPHISMS

Steve Fisk

Bowdoin College
Brunswick, Me 04011, U.S.A.

Abstract

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   F  is a collection of graphs, we say that  F   distinguishes graphs   G   and   H   if there is some member   X   of   F   such that   |G→X |≠|H→X|.  F is a distinguishing family if it distinguishes all pairs of graphs.

We show that various collections of graphs are a distinguishing family.

Keywords: graph homomorphism, chromatic number

1991 Mathematics Subject Classification: 05C15

References

[Lov71]

L. Lovász, On the cancellation law among finite relational structures, Periodica Math. Hung. 1 (1971) 145-156, doi: 10.1007/BF02029172.