Distinguishing graphs by the number of homomorphisms

Steve Fisk

Discussiones Mathematicae Graph Theory (1995)

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

Abstract

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

How to cite

top

Steve 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
  1. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.