The distinguishing index of graphs with at least one cycle is not more than its distinguishing number

Abstract

The distinguishing number (index) $D(G)$ ($D^{\prime }(G)$) of a graph $G$ is the least integer $d$ such that $G$ has an vertex (edge) labeling with $d$ labels that is preserved only by the trivial automorphism. It is known that for every graph $G$ we have $D^{\prime }(G)\le D(G)+1$. The complete characterization of finite trees $T$ with $D^{\prime }(T)=D(T)+1$ has been given recently. In this note we show that if $G$ is a finite connected graph with at least one cycle, then $D^{\prime }(G)\le D(G)$. Finally, we characterize all connected graphs for which $D^{\prime }(G)\le D(G)$.