Geodesic
Endomorphism breaking in graphs
Wilfried Imrich1 ; Rafał Kalinowski2 ; Florian Lehner3 ; Monika Pilśniak2
1Montanuniversität Leoben
2AGH University of Science and Technology
3Technische Universität Graz
The electronic journal of combinatorics, Tome 21 (2014) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/3073
Classification : 05C15, 05C60, 05C25, 05C63, 03E10
Mots-clés : distinguishing number, endomorphisms, infinite graphs

Wilfried Imrich  1   ; Rafał Kalinowski  2   ; Florian Lehner  3   ; Monika Pilśniak  2

1 Montanuniversität Leoben
2 AGH University of Science and Technology
3 Technische Universität Graz 
@article{10_37236_3073,
     author = {Wilfried Imrich and Rafa{\l} Kalinowski and Florian Lehner and Monika Pil\'sniak},
     title = {Endomorphism breaking in graphs},
     journal = {The electronic journal of combinatorics},
     year = {2014},
     volume = {21},
     number = {1},
     doi = {10.37236/3073},
     zbl = {1300.05100},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3073/}
}
TY  - JOUR
AU  - Wilfried Imrich
AU  - Rafał Kalinowski
AU  - Florian Lehner
AU  - Monika Pilśniak
TI  - Endomorphism breaking in graphs
JO  - The electronic journal of combinatorics
PY  - 2014
VL  - 21
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3073/
DO  - 10.37236/3073
ID  - 10_37236_3073
ER  - 
%0 Journal Article
%A Wilfried Imrich
%A Rafał Kalinowski
%A Florian Lehner
%A Monika Pilśniak
%T Endomorphism breaking in graphs
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/3073/
%R 10.37236/3073
%F 10_37236_3073
Wilfried Imrich; Rafał Kalinowski; Florian Lehner; Monika Pilśniak. Endomorphism breaking in graphs. The electronic journal of combinatorics, Tome 21 (2014) no. 1. doi: 10.37236/3073

Cité par Sources :