A class of graphs with distinguishing index ${\mathbf{D}}^{\prime }\le 3$

Abstract

An edge-coloring of a graph is called asymmetric if the only automorphism which preserves it is the identity. Lehner, Pilśniak, and Stawiski proved that all connected regular graphs except $K_2$ admit an asymmetric edge-coloring with three colors. We generalize this result for graphs whose minimal degree $\delta$ and the maximal degree $\Delta$ satisfy $\delta \ge \Delta /2$.