Authors: S. Alikhani, S. Klav¾ar, F. Lehner, S. Soltani Title: Trees with distinguishing index equal distinguishing number plus one Source: Discussiones Mathematicae Graph Theory Received 15.09.2017, Revised 04.07.2018, Accepted 13.07.2018, doi: 10.7151/dmgt.2162 | |
Abstract: 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). | |
Keywords: automorphism group, distinguishing index, distinguishing number, tree, unicyclic graph | |
Links: |