An upper bound on the distinguishing index of graphs with minimum degree at least two

The distinguishing index of a simple graph G, denoted by D'(G), is the least number of labels in an edge labeling of G not preserved by any non-trivial automorphism.  We prove that for a connected graph G with maximum degree \Delta, if  the minimum degree is at least two, then D'(G)\leq \lceil  \sqrt{\Delta }\rceil +۱. We also present graphs G for which D'(G)\leq \lceil  \sqrt{\Delta (G)}\rceil.

کلیدواژه ها:

distinguishing index ، edge-colourings ، upper bound