An upper bound on the distinguishing index of graphs with minimum degree at least two
نویسندگان
1 Department of Mathematics, Yazd University, 89195-741, Yazd, Iran
2 Department of Mathematics, Yazd University, 89195-741, Yazd, Iran
doi
10.22034/AS.2020.1793چکیده
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 +1$. We also present graphs $G$ for which $D'(G)\leq \lceil \sqrt{\Delta (G)}\rceil$.
