Improving upper bounds for the distinguishing index

Abstract

The distinguishing index of a graph G, denoted by Dʹ(G), is the least number of colours in an edge colouring of G not preserved by any non-trivial automorphism. We characterize all connected graphs G with Dʹ(G) ≥ Δ (G). We show that Dʹ(G) ≤ 2 if G is a traceable graph of order at least seven, and Dʹ(G) ≤ 3 if G is either claw-free or 3-connected and planar. We also investigate the Nordhaus-Gaddum type relation: 2 ≤ Dʹ(G) + Dʹ(‾G) ≤ max{Δ (G), Δ (‾G)} + 2 and we confirm it for some classes of graphs.