Endomorphism breaking in graphs (Q405090): Difference between revisions

Summary: 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.