Breaking Symmetry in Graphs by Resolving Sets

Document Type : Original paper

Authors

1 Department of Mathematics, Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran

2 Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

Abstract

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. 

Keywords

Main Subjects

References

[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 distanceedge-monitoring number of graph, Int. J. Found. Comput. Sci. 36 (2025), 901–920. https://doi.org/10.1142/s0129054124500230
Communications in Combinatorics and Optimization
Volume 11, Issue 4
Special issue in honor of Prof. Odile Favaron
December 2026
Pages 1181-1195

Files

Share

How to cite

Statistics