# Distinguishing graphs by the number of homomorphisms

Discussiones Mathematicae Graph Theory (1995)

- Volume: 15, Issue: 1, page 73-75
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topSteve Fisk. "Distinguishing graphs by the number of homomorphisms." Discussiones Mathematicae Graph Theory 15.1 (1995): 73-75. <http://eudml.org/doc/270661>.

@article{SteveFisk1995,

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

author = {Steve Fisk},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph homomorphism; chromatic number; homomorphism; distinguishing family},

language = {eng},

number = {1},

pages = {73-75},

title = {Distinguishing graphs by the number of homomorphisms},

url = {http://eudml.org/doc/270661},

volume = {15},

year = {1995},

}

TY - JOUR

AU - Steve Fisk

TI - Distinguishing graphs by the number of homomorphisms

JO - Discussiones Mathematicae Graph Theory

PY - 1995

VL - 15

IS - 1

SP - 73

EP - 75

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

LA - eng

KW - graph homomorphism; chromatic number; homomorphism; distinguishing family

UR - http://eudml.org/doc/270661

ER -

## References

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

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.