Trees with distinguishing index equal distinguishing number plus one

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$. In this note we characterize trees for which this inequality is sharp. We also show that if $G$ is a connected unicyclic graph, then $D^{\prime }(G)=D(G)$.

9 pages