Geodesic
Trees with Distinguishing Index Equal Distinguishing Number Plus One
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 875-884.

Voir la notice de l'article provenant de la source Library of Science

The distinguishing number (index) D(G) (D′ (G)) of a graph G is the least integer d such that G has an vertex (edge) labeling with d labels that is preserved only by the trivial automorphism. It is known that for every graph G we have D′ (G) ≤ D(G) + 1. In this note we characterize finite trees for which this inequality is sharp. We also show that if G is a connected unicyclic graph, then D′ (G) = D(G).
Keywords: automorphism group, distinguishing index, distinguishing number, tree, unicyclic graph 
@article{DMGT_2020_40_3_a11,
     author = {Alikhani, Saeid and Klav\v{z}ar, Sandi and Lehner, Florian and Soltani, Samaneh},
     title = {Trees with {Distinguishing} {Index} {Equal} {Distinguishing} {Number} {Plus} {One}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {875--884},
     publisher = {mathdoc},
     volume = {40},
     number = {3},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a11/}
}
TY  - JOUR
AU  - Alikhani, Saeid
AU  - Klavžar, Sandi
AU  - Lehner, Florian
AU  - Soltani, Samaneh
TI  - Trees with Distinguishing Index Equal Distinguishing Number Plus One
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 875
EP  - 884
VL  - 40
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a11/
LA  - en
ID  - DMGT_2020_40_3_a11
ER  - 
%0 Journal Article
%A Alikhani, Saeid
%A Klavžar, Sandi
%A Lehner, Florian
%A Soltani, Samaneh
%T Trees with Distinguishing Index Equal Distinguishing Number Plus One
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 875-884
%V 40
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a11/
%G en
%F DMGT_2020_40_3_a11
Alikhani, Saeid; Klavžar, Sandi; Lehner, Florian; Soltani, Samaneh. Trees with Distinguishing Index Equal Distinguishing Number Plus One. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 875-884. http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a11/

[1] M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996) #R18.

[2] S. Alikhani and S. Soltani, Distinguishing number and distinguishing index of certain graphs, Filomat 31 (2017) 4393–4404. doi:10.2298/FIL1714393A

[3] V. Arvind, C. Cheng and N. Devanur, On computing the distinguishing numbers of planar graphs and beyond: a counting approach, SIAM J. Discrete Math. 22 (2008) 1297–1324. doi:10.1137/07068686X

[4] V. Arvind and N. Devanur, Symmetry breaking in trees and planar graphs by vertex coloring, in: Proceedings of the 8th Nordic Combinatorial Conference (Aalborg University, Aalborg, Denmark, 2004).

[5] M. Cavers and K. Seyffarth, Graphs with large distinguishing chromatic number, Electron. J. Combin. 20 (2013) #P19.

[6] M. Chan, The distinguishing number of the augmented cube and hypercube powers, Discrete Math. 308 (2008) 2330–2336. doi:10.1016/j.disc.2006.09.056

[7] C. Cheng, On computing the distinguishing numbers of trees and forests, Electron. J. Combin. 13 (2006) #R11.

[8] K.L. Collins and A.N. Trenk, The distinguishing chromatic number, Electron. J. Combin. 13 (2016) #R16.

[9] E. Estaji, W. Imrich, R. Kalinowski, M. Pilśniak and T. Tucker, Distinguishing Cartesian products of countable graphs, Discuss. Math. Graph Theory 37 (2017) 155–164. doi:10.7151/dmgt.1902

[10] S. Gravier, K. Meslem, S. Schmidt and S. Slimani, A new game invariant of graphs: the game distinguishing number, Discrete Math. Theor. Comput. Sci. 19 (1) (2017) Paper No. 2. doi:10.23638/DMTCS-19-1-2

[11] P. Immel and P.S. Wenger, The list distinguishing number equals the distinguishing number for interval graphs, Discuss. Math. Graph Theory 37 (2017) 165–174. doi:10.7151/dmgt.1927

[12] W. Imrich, R. Kalinowski, M. Pilśniak and M.H. Shekarriz, Bounds for distinguishing invariants of infinite graphs, Electron. J. Combin. 24 (2017) #P3.6.

[13] R. Kalinowski and M. Pilśniak, Distinguishing graphs by edge colourings, European J. Combin. 45 (2015) 124–131. doi:10.1016/j.ejc.2014.11.003

[14] S. Klavžar, T.-L. Wong and X. Zhu, Distinguishing labelings of group action on vector spaces and graphs, J. Algebra 303 (2006) 626–641. doi:10.1016/j.jalgebra.2006.01.045

[15] D. Kim, Y.S. Kwon and J. Lee, The distinguishing numbers of Merged Johnson graphs, Bull. Korean Math. Soc. 52 (2015) 395–408. doi:10.4134/BKMS.2015.52.2.395

[16] C. Laflamme, L. Nguyen Van Thé and N. Sauer, Distinguishing number of countable homogeneous relational structures, Electron. J. Combin. 17 (2010) #R20.

[17] F. Lehner, Distinguishing graphs with intermediate growth, Combinatorica 36 (2016) 333–347. doi:10.1007/s00493-015-3071-5

[18] F. Lehner, Breaking graph symmetries by edge colourings, J. Combin. Theory Ser. B 127 (2017) 205–214. doi:10.1016/j.jctb.2017.06.001

[19] F. Lehner and S.M. Smith, On symmetries of edge and vertex colourings of graphs, preprint.

[20] R. Schmidt, Ein Ordnungsbegriff für Graphen ohne unendliche Wege mit einer Anwendung auf n-fach zusammenhaengende Graphen, Arch. Math. 40 (1983) 283–288. doi:10.1007/BF01192782

[21] S.M. Smith and M.E. Watkins, Bounding the distinguishing number of infinite graphs and permutation groups, Electron. J. Combin. 21 (2014) #P3.40.

[22] M. Watkins and X. Zhou, Distinguishability of locally finite trees, Electron. J. Combin. 14 (2007) #R29.

[23] T.-L. Wong and X. Zhu, Distinguishing labeling of group actions, Discrete Math. 309 (2009) 1760–1765. doi:10.1016/j.disc.2008.02.022