Improving upper bounds for the distinguishing index - Pilśniak, Monika (Ars mathematica contemporanea, 2017)
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^′(\overline{G})≤ \max\{Δ(G),Δ(\overline{G})\}+2$? and we confirm it for some classes of graphs.
Keywords: barvanje povezav; graf brez trizobov; ravninski graf; razlikovalni indeks; zlom simetrije v grafu