A Comprehensive Survey on the Metric Dimension Problem of Graphs and Its Types

Basma Mohamed

doi:doi:10.11648/j.ijtam.20230901.11

| Peer-Reviewed

A Comprehensive Survey on the Metric Dimension Problem of Graphs and Its Types

Basma Mohamed

Published in International Journal of Theoretical and Applied Mathematics (Volume 9, Issue 1)

Received: 20 June 2023 Accepted: 5 July 2023 Published: 13 July 2023

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

Consider a robot that is navigating a graph-based environment and trying to figure out where it is at the moment. It can send a signal to determine how far away it is from every set of fixed landmarks. We address the problem of finding exactly the minimum number of landmarks required and their perfect placement to make sure the robot can always locate itself. The graph's metric dimension is the quantity of landmarks, and the graph's metric basis is the set of nodes on which they are distributed. The metric dimension of a graph is the smallest set of nodes needed to uniquely identify every other node using the shortest path distances. Optimization, network theory, navigation, pattern recognition, image processing, locating the origin of a spread in a network, canonically labeling graphs, and embedding symbolic data in low-dimensional Euclidean spaces are a few examples of applications for metric dimension. Also, Due to its many and varied applications in fields like social sciences, communications networks, algorithmic designs, and others, the study of dominance is the kind of metric dimension that is developing at the fastest rate. This survey provides a self-contained introduction to the metric dimension and an overview of several metric dimension results and applications. We also present algorithms for computing the metric dimension of families of graphs.

Published in	International Journal of Theoretical and Applied Mathematics (Volume 9, Issue 1)
DOI	10.11648/j.ijtam.20230901.11
Page(s)	1-5
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2023. Published by Science Publishing Group

Keywords

Metric Dimension, Resolving Set, Double Resolving Set, Edge Metric Dimension

References

[1]	L. Eroh, C. X. Kang and Y. Eunjeong, "The connected metric dimension at a vertex of a graph," Theoretical Computer Science, vol. 806, pp. 53-69, 2020.
[2]	P. J. Slater, "Leaves of Trees," Congressus Numerantium, vol. 14, pp. 549-559, 1975.
[3]	P. J. Slater, “Dominating and Reference Sets in Graphs,” Journal of Mathematical Physics, vol. 22, no. 4, pp. 445-455, 1998.
[4]	F. Harary and R. A. Melter, “On the Metric Dimension of a Graph,” Ars Combinatoria, vol. 2, pp. 191- 195, 1976.
[5]	M. M. Nezhad, F. Rahbarnia, M. Mirzavaziri AND R. Ghanbari "A Characterization for Metric Two-Dimensional Graphs and Their Enumeration," Journal of Algebraic Systems, vol. 7, no. 2, pp 179-187, 2020.
[6]	H. Pan, M. Ali, G. Ali, M. T. Rahim AND X. Yang "On the Families of Graphs With Unbounded Metric Dimension," IEEE ACCESS, vol. 7, pp. 165060-165064, 2019.
[7]	M. Hussain and Aqsa Farooq "Metric Dimension on Line Graph of Honeycomb Networks" International Journal of Mathematical and Computational Sciences, vol. 13, no. 11, 2019.
[8]	Danang Triantoro Murdiansyah and Adiwijaya "Computing The Metric Dimension of Hypercube Graphs by Particle Swarm Optimization Algorithms," In Recent Advances on Soft Computing and Data Mining: The Second International Conference on Soft Computing and Data Mining (SCDM-2016), Bandung, Indonesia, August 18-20, 2016 Proceedings Second (pp. 171-178). Springer International Publishing.
[9]	Mulyono and Wulandari "The metric dimension of friendship graph Fn, lollipop graph Lm,n and petersen graph Pn,m," Bulletin of Mathematics, vol. 8, no. 2, pp. 117-124, 2016.
[10]	H. Fernau,, P. Heggernes,, P. 't Hof, D. Meistera and R. Saei, "Computing the metric dimension for chain graphs," Information Processing Letters, vol. 115, no. 9, pp. 671-676, 2015.
[11]	I. J. L. Garces and J. B. Rosario, "Computing the Metric Dimension of Truncated Wheels," Applied Mathematical Sciences, vol. 9, no. 56, pp. 2761-2767, 2015.
[12]	C. Zhang, G. Haidar, M. U. I. Khan, F. Yousafzai, K. Hila and A. U. I. Khan, "Constant time calculation of the metric dimension of the join of path graphs," Symmetry, vol. 15, no. 3, p. 708, 2023.
[13]	B. Mohamed and M. Amin, "The Metric Dimension of Subdivisions of Lilly Graph, Tadpole Graph and Special Trees," Applied and Computational Mathematics, vol. 12, no. 1, pp. 9-14, 2023.
[14]	S. Nawaz, M. Ali, M. A. Khan and S. Khan, "Computing metric dimension of power of total graph," IEEE Access, vol. 9, pp. 74550-74561, 2021.
[15]	A. Ahmad, M. Bača and S. Sultan, "Computing the metric dimension of kayak paddles graph and cycles with chord," Proyecciones (Antofagasta), vol. 39, no. 2, pp. 287-300, 2020.
[16]	S. U. Rehman, M. Imran and I. Javaid, "On the metric dimension of arithmetic graph of a composite number," Symmetry, vol. 12, no. 4, p. 607, 2020.
[17]	M. Imran, S. A. U. H. Bokhary and A. Q. Baig, "On families of convex polytopes with constant metric dimension," Computers & Mathematics with Applications, vol. 60, no. 9, pp. 2629-2638, 2010.
[18]	N. Mladenović, J. Kratica, V. Kovačević-Vujčić and M. Čangalović," Variable neighborhood search for metric dimension and minimal doubly resolving set problems," European Journal of Operational Research, vol. 220, no. 2, pp. 328-337, 2012.
[19]	J. Kratica, V. Kovačević-Vujčić and M. Čangalović, "Computing the metric dimension of graphs by genetic algorithms," Computational Optimization and Applications, vol. 44, no. (2), pp. 343-361, 2009.
[20]	G. Jäger and F. Drewes, "The metric dimension of Zn× Zn× Zn is (3n/2) ", Theoretical Computer Science, vol. 806, pp. 344-362, 2020.‏
[21]	M. Imran, M. K. Siddiqui and R. Naeem, “On the metric dimension of generalized petersen multigraphs”, IEEE Access, Vol. 6, pp. 74328-74338, 2018.
[22]	M. F. Nadeem, S. Qu, A. Ahmad and M. Azeem, "Metric dimension of some generalized families of toeplitz graphs," Mathematical Problems in Engineering, vol. 2022, 2022.
[23]	M. Korivand, K. Khashyarmanesh and M. Tavakoli, "Metric Dimension Threshold of Graphs,"Journal of Mathematics, vol. 2022, 2022.
[24]	S. Li, J. B. Liu and M. Munir,"On the metric dimension of generalized tensor product of interval with paths and cycles," Journal of Mathematics, vol. 2020, pp. 1-6, 2020.
[25]	S. Nazeer, M. Hussain, F. A. Alrawajeh and S. Almotairi, "Metric dimension on path-related graphs," Mathematical Problems in Engineering, vol. 2021, pp. 1-12, 2021.
[26]	S. T. Hedetniemi, R. C. Laskar and H. M. Mulder, "New resolvability parameters of graphs," AKCE International Journal of Graphs and Combinatorics, vol. 17, no. 3, pp. 1028-1038, 2020.
[27]	J. Kratica, V. Kovačević-Vujčić and M. Čangalović "Computing Strong Metric Dimension of Some Special Classes of Graphs by Genetic Algorithms," Yugoslav Journal of Operations Research, vol. 18 no. 2, pp. 143-151, 2008.
[28]	J. B. Liu, A. Zafari and H. Zarei, "Metric dimension, minimal doubly resolving sets and the strong metric dimension for jellyfish graph and cocktail party graph," Complexity, vol. 2020, pp. 1-7, 2020.
[29]	M. Ahmad, N. Ameen, Z. Zahid and S. Zafar, "Computing edge version of metric and double metric dimensions of kayak paddle graphs," Discrete Mathematics, Algorithms and Applications, vol. 12, no. 5, 2020.
[30]	J. B. Liu, and A. Zafari, "Some resolving parameters in a class of Cayley graphs," Journal of Mathematics, vol. 2022, pp. 1-5, 2022.
[31]	I. M. Hasibuan, A. N. M. Salman and S. W. Saputro, "The non-isolated resolving number of a graph Cartesian product with a complete graph," Acta Mathematica Universitatis Comenianae, vol. 91, no. 3, pp. 1-14, 2022.
[32]	F. Okamoto, B. Phinezy and P. Zhang," The local metric dimension of a graph,"Mathematica Bohemica, vol. 135, no. 3, pp. 239-255. 2010.
[33]	Juan A. Rodríguez-Velázquez, Gabriel A. Barragán-Ramírez and Carlos García Gómez " On the Local Metric Dimension of Corona Product Graphs" Bulletin of the Malaysian Mathematical Sciences Society, vol. 39, no. 1, pp 157-173, 2016.
[34]	C. Wei, M. Salman, S. Shahzaib, M. U. Rehman and J. Fang, "Classes of planar graphs with constant edge metric dimension," Complexity, vol. 2021, pp. 1-10, 2021.
[35]	G. A. Barragán-Ramírez and J. A. Rodríguez-Velázquez, "The local metric dimension of strong product graphs," Graphs and Combinatorics, vol. 32, pp. 1263-1278, 2016.
[36]	K. N. Meera, and B. Sooryanarayana, "Radiatic dimension of a graph," Journal of Computations and Modelling, vol. 2, no. 4, pp. 1-23, 2012.
[37]	Marsidi, Ika Hesti Agustin, Dafik, Ridho Alfarisi and Hendrik Siswono "On The Metric Dimension of Some Operation Graphs" CAUCHY - Jurnal Matematika Murni dan Aplikasi, vol. 5, no. 3, pp. 88-94, 2018.
[38]	M. Feng and K. Wang "On the metric dimension and fractional metric dimension of the hierarchical product of graphs,"Appl. Anal. Discrete Math, vol. 7, pp. 302–313, 2013.
[39]	J. A. Rodríguez-Velázquez, C. García Gómez and G. A. Barragán-Ramírez, "Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs," International Journal of Computer Mathematics, vol. 92, no. 4, pp. 686-693, 2015.
[40]	W. T. Budianto and T. A. Kusmayadi,"The local metric dimension of starbarbell graph, graph, and Mobius ladder graph," In Journal of physics: conference series, vol. 1008, no. 1, p. 012050, IOP Publishing, 2018.
[41]	A. Estrada-Moreno, G. I. Yero and J. A. Rodríguez-Velázquez, "The k-metric dimension of the lexicographic product of graphs," Discrete Mathematics, vol. 339, no. 7, pp. 1924-1934, 2016.
[42]	Jude Annie Cynthia and Ramya "The Local Metric Dimension of Cyclic Split Graph "Annals of Pure and Applied Mathematics, vol. 8, no. 2, pp. 201-205, 2014.
[43]	T. Laihonen, "The metric dimension for resolving several objects," Information Processing Letters, vol. 116, no. 11, pp. 694-700, 2016.
[44]	B. Mohamed and M. Amin, "Domination Number and Secure Resolving Sets in Cyclic Networks," Applied and Computational Mathematics, vol. 12, no. 2, pp. 42-45, 2023.
[45]	B. Mohamed, L. Mohaisen and M. Amin, (2022), "Binary Equilibrium Optimization Algorithm for Computing Connected Domination Metric Dimension Problem," Scientific Programming, vol. 2022, 2022.
[46]	Y. Ramírez-Cruz, A. Estrada-Moreno and J. A. Rodríguez-Velázquez, "The simultaneous metric dimension of families composed by lexicographic product graphs," Graphs and Combinatorics, vol. 32, pp. 2093-2120, 2016.
[47]	B. Mohamed, L. Mohaisen and M. Amin, "Computing Connected Resolvability of Graphs Using Binary Enhanced Harris Hawks Optimization," Intelligent Automation & Soft Computing, vol. 36, no. 2, 2023.
[48]	J. M. Cabaro and H. Rara, "On 2-Resolving Dominating Sets in the Join, Corona and Lexicographic Product of two Graphs," European Journal of Pure and Applied Mathematics, vol. 15, no. 3, pp. 1417-1425, 2022.
[49]	B. Rajan, A. William, I. Rajasingh and S. Prabhu, "On Certain Connected Resolving Parameters of Hypercube Networks," Applied Mathematics, vol. 3, no. 5, pp. 473-477, 2012.
[50]	B. Mohamed, Metric Dimension of Graphs and its Application to Robotic Navigation, vol. 184, no. 15, 2022.
[51]	R. Manjusha and A. S. Kuriakose, "Metric dimension and uncertainty of traversing robots in a network," International Journal on Applications of Graph Theory in Wireless Ad Hoc Networks and Sensor Networks (GRAPH-HOC), vol. 7, pp. 1-9, 2015.
[52]	G. Chartrand, L. Eroh, M. A. Johnson and O. R. Oellermann, "Resolvability in graphs and the metric dimension of a graph", Discrete Applied Mathematics, vol. 105, no. (1-3), pp. 99-113, 2000.‏
[53]	M. Idrees, H. Ma, M. Wu, A. R. Nizami, M. Munir and S. Ali, "Metric dimension of generalized Mobius ladder and its application to wsn localization," Journal of Advanced Computational Intelligence and Intelligent Informatics, vol. 24, no. 1, pp. 3-11, 2020.‏
[54]	A. Sebö and E. Tannier, “On Metric Generators of Graphs,” Mathematics of Operations Research, vol. 29, no. 2, pp. 383-393. 2004.
[55]	S. Söderberg and H. S. Shapiro, "A Combinatory Detection Problem, "American Mathematical Monthly, vol. 70, no. 10, pp. 1066-1070, 1963.

Cite This Article

Plain Text BibTeX RIS

APA Style

Basma Mohamed. (2023). A Comprehensive Survey on the Metric Dimension Problem of Graphs and Its Types. International Journal of Theoretical and Applied Mathematics, 9(1), 1-5. https://doi.org/10.11648/j.ijtam.20230901.11

Copy | Download

ACS Style

Basma Mohamed. A Comprehensive Survey on the Metric Dimension Problem of Graphs and Its Types. Int. J. Theor. Appl. Math. 2023, 9(1), 1-5. doi: 10.11648/j.ijtam.20230901.11

Copy | Download

AMA Style

Basma Mohamed. A Comprehensive Survey on the Metric Dimension Problem of Graphs and Its Types. Int J Theor Appl Math. 2023;9(1):1-5. doi: 10.11648/j.ijtam.20230901.11

Copy | Download

@article{10.11648/j.ijtam.20230901.11,
  author = {Basma Mohamed},
  title = {A Comprehensive Survey on the Metric Dimension Problem of Graphs and Its Types},
  journal = {International Journal of Theoretical and Applied Mathematics},
  volume = {9},
  number = {1},
  pages = {1-5},
  doi = {10.11648/j.ijtam.20230901.11},
  url = {https://doi.org/10.11648/j.ijtam.20230901.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ijtam.20230901.11},
  abstract = {Consider a robot that is navigating a graph-based environment and trying to figure out where it is at the moment. It can send a signal to determine how far away it is from every set of fixed landmarks. We address the problem of finding exactly the minimum number of landmarks required and their perfect placement to make sure the robot can always locate itself. The graph's metric dimension is the quantity of landmarks, and the graph's metric basis is the set of nodes on which they are distributed. The metric dimension of a graph is the smallest set of nodes needed to uniquely identify every other node using the shortest path distances. Optimization, network theory, navigation, pattern recognition, image processing, locating the origin of a spread in a network, canonically labeling graphs, and embedding symbolic data in low-dimensional Euclidean spaces are a few examples of applications for metric dimension. Also, Due to its many and varied applications in fields like social sciences, communications networks, algorithmic designs, and others, the study of dominance is the kind of metric dimension that is developing at the fastest rate. This survey provides a self-contained introduction to the metric dimension and an overview of several metric dimension results and applications. We also present algorithms for computing the metric dimension of families of graphs.},
 year = {2023}
}

Copy | Download

TY  - JOUR
T1  - A Comprehensive Survey on the Metric Dimension Problem of Graphs and Its Types
AU  - Basma Mohamed
Y1  - 2023/07/13
PY  - 2023
N1  - https://doi.org/10.11648/j.ijtam.20230901.11
DO  - 10.11648/j.ijtam.20230901.11
T2  - International Journal of Theoretical and Applied Mathematics
JF  - International Journal of Theoretical and Applied Mathematics
JO  - International Journal of Theoretical and Applied Mathematics
SP  - 1
EP  - 5
PB  - Science Publishing Group
SN  - 2575-5080
UR  - https://doi.org/10.11648/j.ijtam.20230901.11
AB  - Consider a robot that is navigating a graph-based environment and trying to figure out where it is at the moment. It can send a signal to determine how far away it is from every set of fixed landmarks. We address the problem of finding exactly the minimum number of landmarks required and their perfect placement to make sure the robot can always locate itself. The graph's metric dimension is the quantity of landmarks, and the graph's metric basis is the set of nodes on which they are distributed. The metric dimension of a graph is the smallest set of nodes needed to uniquely identify every other node using the shortest path distances. Optimization, network theory, navigation, pattern recognition, image processing, locating the origin of a spread in a network, canonically labeling graphs, and embedding symbolic data in low-dimensional Euclidean spaces are a few examples of applications for metric dimension. Also, Due to its many and varied applications in fields like social sciences, communications networks, algorithmic designs, and others, the study of dominance is the kind of metric dimension that is developing at the fastest rate. This survey provides a self-contained introduction to the metric dimension and an overview of several metric dimension results and applications. We also present algorithms for computing the metric dimension of families of graphs.
VL  - 9
IS  - 1
ER  -

Copy | Download

Author Information

Basma Mohamed

Mathematics and Computer Science Department, Faculty of Science, Menoufia University, Shebin Elkom, Egypt

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Basma Mohamed. (2023). A Comprehensive Survey on the Metric Dimension Problem of Graphs and Its Types. International Journal of Theoretical and Applied Mathematics, 9(1), 1-5. https://doi.org/10.11648/j.ijtam.20230901.11

Copy | Download

ACS Style

Basma Mohamed. A Comprehensive Survey on the Metric Dimension Problem of Graphs and Its Types. Int. J. Theor. Appl. Math. 2023, 9(1), 1-5. doi: 10.11648/j.ijtam.20230901.11

Copy | Download

AMA Style

Basma Mohamed. A Comprehensive Survey on the Metric Dimension Problem of Graphs and Its Types. Int J Theor Appl Math. 2023;9(1):1-5. doi: 10.11648/j.ijtam.20230901.11

Copy | Download

@article{10.11648/j.ijtam.20230901.11,
  author = {Basma Mohamed},
  title = {A Comprehensive Survey on the Metric Dimension Problem of Graphs and Its Types},
  journal = {International Journal of Theoretical and Applied Mathematics},
  volume = {9},
  number = {1},
  pages = {1-5},
  doi = {10.11648/j.ijtam.20230901.11},
  url = {https://doi.org/10.11648/j.ijtam.20230901.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ijtam.20230901.11},
  abstract = {Consider a robot that is navigating a graph-based environment and trying to figure out where it is at the moment. It can send a signal to determine how far away it is from every set of fixed landmarks. We address the problem of finding exactly the minimum number of landmarks required and their perfect placement to make sure the robot can always locate itself. The graph's metric dimension is the quantity of landmarks, and the graph's metric basis is the set of nodes on which they are distributed. The metric dimension of a graph is the smallest set of nodes needed to uniquely identify every other node using the shortest path distances. Optimization, network theory, navigation, pattern recognition, image processing, locating the origin of a spread in a network, canonically labeling graphs, and embedding symbolic data in low-dimensional Euclidean spaces are a few examples of applications for metric dimension. Also, Due to its many and varied applications in fields like social sciences, communications networks, algorithmic designs, and others, the study of dominance is the kind of metric dimension that is developing at the fastest rate. This survey provides a self-contained introduction to the metric dimension and an overview of several metric dimension results and applications. We also present algorithms for computing the metric dimension of families of graphs.},
 year = {2023}
}

Copy | Download

TY  - JOUR
T1  - A Comprehensive Survey on the Metric Dimension Problem of Graphs and Its Types
AU  - Basma Mohamed
Y1  - 2023/07/13
PY  - 2023
N1  - https://doi.org/10.11648/j.ijtam.20230901.11
DO  - 10.11648/j.ijtam.20230901.11
T2  - International Journal of Theoretical and Applied Mathematics
JF  - International Journal of Theoretical and Applied Mathematics
JO  - International Journal of Theoretical and Applied Mathematics
SP  - 1
EP  - 5
PB  - Science Publishing Group
SN  - 2575-5080
UR  - https://doi.org/10.11648/j.ijtam.20230901.11
AB  - Consider a robot that is navigating a graph-based environment and trying to figure out where it is at the moment. It can send a signal to determine how far away it is from every set of fixed landmarks. We address the problem of finding exactly the minimum number of landmarks required and their perfect placement to make sure the robot can always locate itself. The graph's metric dimension is the quantity of landmarks, and the graph's metric basis is the set of nodes on which they are distributed. The metric dimension of a graph is the smallest set of nodes needed to uniquely identify every other node using the shortest path distances. Optimization, network theory, navigation, pattern recognition, image processing, locating the origin of a spread in a network, canonically labeling graphs, and embedding symbolic data in low-dimensional Euclidean spaces are a few examples of applications for metric dimension. Also, Due to its many and varied applications in fields like social sciences, communications networks, algorithmic designs, and others, the study of dominance is the kind of metric dimension that is developing at the fastest rate. This survey provides a self-contained introduction to the metric dimension and an overview of several metric dimension results and applications. We also present algorithms for computing the metric dimension of families of graphs.
VL  - 9
IS  - 1
ER  -

Copy | Download