Download PDF - Distinguishing graphs by the number of homomorphismsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Distinguishing graphs by the number of homomorphisms

Authors 1

Affiliations

  1. Bowdoin College, Brunswick

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 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.

Keywords

ENG
graph homomorphism, chromatic number

Bibliography

  1. [Lov71] L. Lovász, On the cancellation law among finite relational structures, Periodica Math. Hung. 1 (1971) 145-156, doi: 10.1007/BF02029172.
Discussiones Mathematicae Graph Theory
1995/15/1
Export to PBN, Opens in new tab
Pages:
73-75
Main language of publication
English
Received
1994-05-25
Published
1995
Exact and natural sciences