Trees with distinguishing index equal distinguishing number plus one

2016/08/11 by Alikhani, Saeid, Klavžar, Sandi, Lehner, Florian +1
#05C15 #05E18 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1608.03501

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 trees for which this inequality is sharp. We also show that if G is a connected unicyclic graph, then D'(G) = D(G).

Related

• The distinguishing index of graphs with at least one cycle is not more than its distinguishing number
• Distinguishing number and distinguishing index of certain graphs
• Trees with distinguishing number two
• Distinguishing number and distinguishing index of some operations on graphs
• An upper bound on the distinguishing index of graphs with minimum degree at least two