The distinguishing index of infinite graphs

Abstract

The distinguishing index D0(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 D0(G) 6 (G) for an arbitrary infinite graph. Nonetheless, the distinguish- ing 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.