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:
PDF