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

Document Type : Research Paper


Department of Mathematics, Yazd University, 89195-741, Yazd, Iran



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$.


[7] W. Imrich, J. Jerebic, S. Klavˇzar, The distinguishing number of Cartesian products of complete graphs,
European J. Combin., 29 (2008) 922-929.
[8] R. Kalinowski, M. Pil´sniak, Distinguishing graphs by edge colourings, European J. Combin., 45 (2015)
[9] M. Pil´sniak, Improvig upper Bounds for the Distinguishing Index, Ars Math. Contemp., 13 (2017) 259-274.