Improving upper bounds for the distinguishing index

Monika Pilśniak


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.


Edge colouring, symmetry breaking in graph, distinguishing index, claw-free graph, planar graph

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications