The Distinguishing Index of Infinite Graphs

Abstract

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.