An upper bound on the distinguishing index of graphs with minimum degree at least two

Abstract

The distinguishing index of a simple graph $G$, denoted by $D^{\prime }(G)$, is the least number of labels in an edge labeling of $G$ not preserved by any non-trivial automorphism. It was conjectured by Pilśniak (2015) that for any 2-connected graph $D^{\prime }(G)\le \lceil \sqrt{\Delta (G)}\rceil +1$. We prove a more general result for the distinguishing index of graphs with minimum degree at least two from which the conjecture follows. Also we present graphs $G$ for which $D^{\prime }(G)\le \lceil \sqrt{\Delta }\rceil$.

10 pages, 4 figures