2013/11/27 by Wilfried Imrich, Imrich, Wilfried, Rafał Kalinowski +5
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #03E10 #05C25 #05C80 #Advanced Graph Theory Research #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Mathematics #math.CO #msc:03E10 #msc:05C25 #msc:05C80 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1311.6972
17 pages, 2 figures
arxiv created 2013/11/27 · openalex publication_date 2013/11/27 · arxiv updated 2013/11/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce the \it 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. This is the main concern of the paper.