S. Alikhani, S. Klav¾ar, F. Lehner, S. Soltani
Trees with distinguishing index equal distinguishing number plus one
Discussiones Mathematicae Graph Theory
Received 15.09.2017, Revised 04.07.2018, Accepted 13.07.2018, doi: 10.7151/dmgt.2162
The distinguishing number (index) D(G) (D'(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'(G) ≤ D(G) + 1. In this note we characterize finite trees for which this inequality is sharp. We also show that if G is a connected unicyclic graph, then D'(G) = D(G).
automorphism group, distinguishing index, distinguishing number, tree, unicyclic graph