DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory  15(1) (1995)   73-75
DOI: 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.