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


[1] M.O. Albertson, K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996), #R18.
[2] S. Alikhani, S. Klavzar, F. Lehner, S. Soltani, Trees with distinguishing index equal distinguishing number plus one, Discuss. Math. Graph Theory, 40 (2020) 875-884.
[3] S. Alikhani, S. Soltani, Distinguishing number and distinguishing index of certain graphs, Filomat, 31:14 (2017), 4393-4404.
[4] G. Chartrand, H. Escuadro, F. Okamoto, P. Zhang, Detectable colorings of graphs, Utilitas Math. 69 (2006), 13-32.
[5] M. J. Fisher, G. Isaak, Distinguishing colorings of Cartesian products of complete graphs, Discrete Math. 308 (11) (2008), 2240-2246.
[6] R. Hammack, W. Imrich and S. Klavzar, Handbook of product graphs (second edition), Taylor & Francis group, 2011.
[7] W. Imrich, J. Jerebic, S. Klavzar, The distinguishing number of Cartesian products of complete graphs, European J. Combin. 29 (2008), 922-929.
[8] R. Kalinowski, M. Pilsniak, Distinguishing graphs by edge colourings, European J. Combin. 45 (2015), 124-131.
[9] M. Pilsniak, Improvig upper Bounds for the Distinguishing Index, Ars Math. Contemp. 13 (2017), 259-274.