Endomorphism Breaking in Graphs

Wilfried Imrich, Rafał Kalinowski, Florian Lehner, Monika Pilśniak

Research output: Contribution to journalArticlepeer-review


We introduce the endomorphism distinguishing number De(G) of a graph G as the least cardinal d such that G has a vertex coloring with d colors that is only preserved by the trivial endomorphism. This generalizes the notion of the distinguishing number D(G) of a graph G, which is defined for automorphisms instead of endomorphisms.

As the number of endomorphisms can vastly exceed the number of automorphisms, the new concept opens challenging problems, several of which are presented here. In particular, we investigate relationships between De(G) and the endomorphism motion of a graph G, that is, the least possible number of vertices moved by a nontrivial endomorphism of G. Moreover, we extend numerous results about the distinguishing number of finite and infinite graphs to the endomorphism distinguishing number.
Original languageEnglish
Article numberP1.16
Number of pages13
JournalThe Electronic Journal of Combinatorics
Issue number1
Publication statusPublished - 2014

Fields of Expertise

  • Sonstiges


Dive into the research topics of 'Endomorphism Breaking in Graphs'. Together they form a unique fingerprint.

Cite this