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

Document Type : Research Paper

Authors

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

Abstract

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

Keywords

References

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

Files

Share

How to cite

Statistics