The distinguishing index of connected graphs without pendant edges
Wilfried Imrich, Rafał Kalinowski, Monika Pilśniak, Mariusz Woźniak · 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) ≤ Δ for every countable, connected graph G with finite maximum degree Δ except for three small cycles. We prove that D′(G) ≤ ⌈√Δ⌉ + 1 if additionally G does not have pendant edges.