The distinguishing index $D^\prime(G)$ of a graph $G$ is the least cardinal $d$ such that $G$ has an edge colouring with $d$ colours that is only preserved by the trivial automorphism. This is similar to the notion of the distinguishing number $D(G)$ of a graph $G$, which is defined with respect to vertex colourings.We derive several bounds for infinite graphs, in particular, we prove the general bound $D^\prime(G)\leq\Delta(G)$ for an arbitrary infinite graph. Nonetheless, the distinguishing index is at most two for many countable graphs, also for the infinite random graph and for uncountable tree-like graphs.We also investigate the concept of the motion of edges and its relationship with the Infinite Motion Lemma.
@article{10_37236_3933,
author = {Izak Broere and Monika Pil\'sniak},
title = {The distinguishing index of infinite graphs},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {1},
doi = {10.37236/3933},
zbl = {1310.05147},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3933/}
}
TY - JOUR
AU - Izak Broere
AU - Monika Pilśniak
TI - The distinguishing index of infinite graphs
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/3933/
DO - 10.37236/3933
ID - 10_37236_3933
ER -
%0 Journal Article
%A Izak Broere
%A Monika Pilśniak
%T The distinguishing index of infinite graphs
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/3933/
%R 10.37236/3933
%F 10_37236_3933
Izak Broere; Monika Pilśniak. The distinguishing index of infinite graphs. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/3933
