Distinguishing graphs by the number of homomorphisms

• Autorzy: Steve Fisk
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

graph homomorphism; chromatic number

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1995
• Tom: 15
• Numer: 1
• Strony: 73-75

Daty

wydano

1995

otrzymano

1994-05-25

Twórcy

autor

Steve Fisk

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

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1008