Breaking symmetry in graphs by resolving sets

Soltankhah, Nasrin; Korivand, Meysam; Klavžar, Sandi

doi:10.22049/cco.2026.30820.2632

تعداد نشریات	6
تعداد شماره‌ها	131
تعداد مقالات	1,634
تعداد مشاهده مقاله	1,899,064
تعداد دریافت فایل اصل مقاله	1,758,846

	Breaking symmetry in graphs by resolving sets
Communications in Combinatorics and Optimization
مقاله 11، دوره 11، شماره 4، اسفند 2026، صفحه 1181-1195 اصل مقاله (415.74 K)
نوع مقاله: Original paper
شناسه دیجیتال (DOI): 10.22049/cco.2026.30820.2632
نویسندگان
Nasrin Soltankhah^* ¹؛ Meysam Korivand²؛ Sandi Klavžar³
¹Department of Mathematics, Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran
²Department of Mathematics, Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran
³Faculty of Mathematics and Physics, University of Ljubljana, Slovenia
چکیده
Let $dim(G)$ and $D(G)$ respectively denote the metric dimension and the distinguishing number of a graph $G$. It is proved that $D(G) \le dim(G)+1$ holds for every connected graph $G$. Among trees, exactly paths and stars attain the bound, and among connected unicyclic graphs such graphs are $t$-cycles for $t\in \{3,4,5\}$. It is shown that for any $1\leq n< m$, there exists a graph $G$ with $D(G)=n$ and ${\rm dim}(G)=m$. Using the bound $D(G) \le dim(G)+1$, graphs with $D(G) = n(G)-2$ are classified.
کلیدواژه‌ها
resolving set؛ metric dimension؛ distinguishing number؛ twin graph؛ almost asymmetric graph

مراجع
[1] B. Ahmadi, F. Alinaghipour, and M.H. Shekarriz, Number of distinguishing colorings and partitions, Discrete Math. 343 (2020), 111984. https://doi.org/10.1016/j.disc.2020.111984 [2] M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996), # 18. https://doi.org/10.37236/1242 [3] S. Arumugam and V. Mathew, The fractional metric dimension of graphs, Discrete Math. 312 (2012), 1584–1590. https://doi.org/10.1016/j.disc.2011.05.039 [4] L. Babai, Asymmetric trees with two prescribed degrees, Acta Math. Acad. Sci. Hungar. 29 (1977), 193–200. https://doi.org/10.1007/bf01896481 [5] L. Babai, Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker’s conjecture confirmed, J. Algebra 607 (2022), 64–106. https://doi.org/10.1016/j.jalgebra.2021.10.033 [6] R.F. Bailey and P.J. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bull. London Math. Soc. 43 (2011), 209–242. https://doi.org/10.1112/blms/bdq096 [7] D.L. Boutin, Determining sets, resolving sets, and the exchange property, Graphs Combin. 25 (2009), 789–806. https://doi.org/10.1007/s00373-010-0880-6 [8] M. Chan, The distinguishing number of the direct product and wreath product action, J. Algebraic Combin. 24 (2006), 331–345. https://doi.org/10.1007/s10801-006-0006-7 [9] G. Chartrand, L. Eroh, M.A. Johnson, and O.R. Ollermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2002), 99–113. https://doi.org/10.1016/s0166-218x(00)00198-0 [10] K.L. Collins and A.N. Trenk, The distinguishing chromatic number, Electron. J. Combin. 13 (2006), #R16. https://doi.org/10.37236/1042 [11] K.L. Collins and A.N. Trenk, The distinguishing number and distinguishing chromatic number for posets, Order 39 (2022), 361–380. https://doi.org/10.1007/s11083-021-09583-2 [12] A. Estrada-Moreno, I.G. Yero, and J.A. Rodríguez-Velázquez, The $k$-metric dimension of a graph, Appl. Math. Inf. Sci. 9 (2015), 2829–2840. [13] D. Garijo, A. González, and A. Márquez, The difference between the metric dimension and the determining number of a graph, Appl. Math. Comput. 249 (2014), 487–501. https://doi.org/10.1016/j.amc.2014.10.034 [14] A. Hakanen, V. Junnila, T. Laihonen, and I.G. Yero, On vertices contained in all or in no metric basis, Discrete Appl. Math. 319 (2022), 407–423. https://doi.org/10.1016/j.dam.2021.12.004 [15] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191–195. [16] C. Hernando, M. Mora, I.M. Pelayo, C. Seara, and D.R. Wood, Extremal graph theory for metric dimension and diameter, Electron. J. Combin. 17 (2010), #R30. https://doi.org/10.37236/302 [17] W. Imrich and S. Klavžar, Distinguishing Cartesian powers of graphs, J. Graph Theory 53 (2006), 250–260. [18] F. Jamil, A. Kashif, and S. Zafar, Fractional strong metric dimension of convex polytopes and its applications, Hacet. J. Math. Stat. 54 (2025), 389–403. https://doi.org/10.15672/hujms.1211776 [19] M. Jannesari and B. Omoomi, The metric dimension of the lexicographic product of graphs, Discrete Math. 312 (2012), 3349–3356. https://doi.org/10.1016/j.disc.2012.07.025 [20] M. Jannesari and B. Omoomi, Characterization of $n$-vertex graphs with metric dimension $n-3$, Math. Bohem. 139 (2014), 1–23. https://doi.org/10.21136/mb.2014.143632 [21] R. Kalinowski and M. Pilśniak, Distinguishing graphs by edge colourings, European J. Combin. 45 (2015), 124–131. https://doi.org/10.1016/j.ejc.2014.11.003 [22] R. Kalinowski, M. Pilśniak, and M. Prorok, Distinguishing arc-colourings of symmetric digraphs, Art Discrete Appl. Math. 6 (2023), #P2.04. https://doi.org/10.26493/2590-9770.1472.24b [23] A. Kelenc, D. Kuziak, A. Taranenko, and I.G. Yero, Mixed metric dimension of graphs, Appl. Math. Comput. 314 (2017), 429–438. https://doi.org/10.1016/j.amc.2017.07.027 [24] A. Kelenc, N. Tratnik, and I.G. Yero, Uniquely identifying the edges of a graph: the edge metric dimension, Discrete Appl. Math. 251 (2018), 204–220. https://doi.org/10.1016/j.dam.2018.05.052 [25] S. Khuller, B. Raghavachari, and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996), 217–229. https://doi.org/10.1016/0166-218x(95)00106-2 [26] S. Klavžar and D. Kuziak, Nonlocal metric dimension of graphs, Bull. Malays. Math. Sci. Soc. 46 (2023), Article Number: 66. https://doi.org/10.1007/s40840-022-01459-x [27] S. Klavžar, T.-L. Wong, and X. Zhu, Distinguishing labellings of group action on vector spaces and graphs, J. Algebra 303 (2006), 626–641. https://doi.org/10.1016/j.jalgebra.2006.01.045 [28] D. Kuziak and I.G. Yero, Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results, arXiv:2107.04877 [math.CO] (2021). [29] F. Okamoto, B. Phinezy, and P. Zhang, The local metric dimension of a graph, Math. Bohem. 135 (2010), 239–255. https://doi.org/10.21136/mb.2010.140702 [30] A. Russell and R. Sundaram, A note on the asymptotics and computational complexity of graph distinguishability, Electron. J. Combin. 5 (1998), #R23. https://doi.org/10.37236/1361 [31] A. Sebö and E. Tannier, On metric generators of graphs, Math. Oper. Res. 29 (2004), 383–393. https://doi.org/10.1287/moor.1030.0070 [32] B. Shanmukha, B. Sooryanarayana, and K.S. Harinath, Metric dimension of wheels, Far East J. Appl. Math. 8 (2002), 217–229. [33] M.H. Shekarriz, B. Ahmadi, S.A. Talebpour, and M.H. Shirdareh Haghighi, Distinguishing threshold of graphs, J. Graph Theory 103 (2023), 359–377. https://doi.org/10.1002/jgt.22923 [34] P.J. Slater, Leaves of trees, Congress. Numer. 14 (1975), 549–559. [35] R.C. Tillquist, R.M. Frongillo, and M.E. Lladser, Getting the lay of the land in discrete space: A survey of metric dimension, its applications, SIAM Rev. 65 (2023), 919–962. https://doi.org/10.1137/21m1409512 [36] R.C. Tillquist and M.E. Lladser, Low-dimensional representation of genomic sequences, J. Math. Biol. 79 (2019), 1–29. https://doi.org/10.1007/s00285-019-01348-1 [37] R. Trujillo-Rasua and I.G. Yero, $k$-metric antidimension: A privacy measure for social graphs, Inf. Sci. 328 (2016), 403–417. https://doi.org/10.1016/j.ins.2015.08.048 [38] T.W. Tucker, Distinguishing maps, Electron. J. Combin. 18 (2011), #50. https://doi.org/10.37236/537 [39] J. Tymoczko, Distinguishing numbers for graphs and groups, Electron. J. Combin. 11 (2004), #R63. https://doi.org/10.37236/1816 [40] J. Wang, F. Tian, Y. Liu, J. Pang, and L. Miao, On graphs of order $n$ with metric dimension $n-4$, Graphs Combin. 39 (2023), Article number: 29. https://doi.org/10.1007/s00373-023–02627-x [41] C. Yang, Z. Ji, W. Li, and Y. Liang, The local metric dimension and distance-edge-monitoring number of graph, Int. J. Found. Comput. Sci. 36 (2025), 901–920. https://doi.org/10.1142/s0129054124500230
آمار تعداد مشاهده مقاله: 416 تعداد دریافت فایل اصل مقاله: 245

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

آمار

Breaking symmetry in graphs by resolving sets