The distinguishing index of connected graphs without pendant edges - Imrich, Wilfried (Ars mathematica contemporanea, 2020)
We consider edge colourings, not necessarily proper. The distinguishing index ?$D'(G)$? of a graph ?$G$? is the least number of colours in an edge colouring that is preserved only by the identity automorphism. It is known that ?$D'(G) \le Δ$? for every countable, connected graph ?$G$? with finite maximum degree ?$Δ$? except for three small cycles. We prove that ?$D'(G) \le \lceil\sqrt{Δ}\rceil+1$? if additionally ?$G$? does not have pendant edges.
Keywords: distinguishing index of a graph; razlikovalni indeks grafa; symmetry breaking; zlom simetrije