Endomorphism Breaking in Graphs

Citations Over TimeTop 11% of 2014 papers

Abstract

We introduce the endomorphism distinguishing number $D_e(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 $D_e(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.

Related Papers

• → The automorphisms of endomorphism semigroups of free burnside groups(2015)6 cited
• → On semigroups of order-preserving transformations of countable linearly ordered sets(2009)3 cited
• → Endomorphism rings and automorphism groups of almost completely decomposable groups(2000)14 cited
• → The automorphisms of endomorphism semigroups of relatively free groups(2018)3 cited
• → Split Metacyclic p-Groups That Are A-E Groups(1999)