Uniquely identifying vertices and edges of a heptagonal snake graph using distance formulas

Fozia Bashir Farooq; Furqan Ahmad; Muhammad Kamran Jamil; Aisha Javed; Nouf Abdulrahman Alqahtani; Fozia Bashir Farooq; Furqan Ahmad; Muhammad Kamran Jamil; Aisha Javed; Nouf Abdulrahman Alqahtani

doi:10.3934/math.2025676

AIMS Mathematics

2025, Volume 10, Issue 6: 15069-15087. doi: 10.3934/math.2025676

Previous Article Next Article

Research article Special Issues

Uniquely identifying vertices and edges of a heptagonal snake graph using distance formulas

1.
Department of Mathematics and Statistics, College of Science, Imam Mohammad Ibn Saud Islamic University (IMSIU), Saudi Arabia
2.
Department of Mathematics, Riphah International University, Lahore, Pakistan
3.
Abdus Salam School of Mathematical Sciences, GCU, Lahore, Pakistan

Received: 21 March 2025 Revised: 27 May 2025 Accepted: 10 June 2025 Published: 30 June 2025
MSC : 05C12, 05C90

Consider a city with a network of roads where surveillance cameras are positioned at key intersections. To uniquely determine the position of any car, the minimal number of cameras needed is determined by using the metric dimension of the network. Similarly, if we desire to differentiate each individual road segment using cameras, we depend on the edge metric dimension. These concepts are essential in applications such as transportation planning, autonomous navigation and network monitoring. Let $ G = (V(G), E(G)) $ be a connected graph with vertex set $ V(G) $ and edge set $ E(G) $, a subset $ R\subseteq V(G) $ is called a resolving set, if each vertex of $ G $ has unique distance with respect to $ R $. The cardinality of the smallest resolving set is called the metric dimension, denoted as $ dim(G) $. Similarly, a set of vertices $ R \subseteq V(G) $ is called an edge resolving set if for every pair of distinct edges $ e_1, e_2 \in E(G) $, there exists a vertex $ v \in R $ such that $ d(e_1, v) \neq d(e_2, v) $, where $ d(e, v) $ is defined as $ d(e = uw, v) = \min\{ d(u, v), d(w, v) \} $. The edge metric dimension is defined as the number of elements in the smallest edge resolving set. Finding these dimensions is an NP-hard problem, making efficient computations precious. In this article, we explored the metric dimension, edge metric dimension, partition dimension and edge partition dimension of the heptagonal snake graph $ (HPS_k) $.
- metric dimension,
- resolving set,
- edge metric dimension,
- edge resolving set,
- partition dimension,
- partition resolving set,
- edge partition dimension,
- edge partition resolving set,
- heptagonal snake graph
Citation: Fozia Bashir Farooq, Furqan Ahmad, Muhammad Kamran Jamil, Aisha Javed, Nouf Abdulrahman Alqahtani. Uniquely identifying vertices and edges of a heptagonal snake graph using distance formulas[J]. AIMS Mathematics, 2025, 10(6): 15069-15087. doi: 10.3934/math.2025676

Related Papers:

Abstract

Consider a city with a network of roads where surveillance cameras are positioned at key intersections. To uniquely determine the position of any car, the minimal number of cameras needed is determined by using the metric dimension of the network. Similarly, if we desire to differentiate each individual road segment using cameras, we depend on the edge metric dimension. These concepts are essential in applications such as transportation planning, autonomous navigation and network monitoring. Let $ G = (V(G), E(G)) $ be a connected graph with vertex set $ V(G) $ and edge set $ E(G) $, a subset $ R\subseteq V(G) $ is called a resolving set, if each vertex of $ G $ has unique distance with respect to $ R $. The cardinality of the smallest resolving set is called the metric dimension, denoted as $ dim(G) $. Similarly, a set of vertices $ R \subseteq V(G) $ is called an edge resolving set if for every pair of distinct edges $ e_1, e_2 \in E(G) $, there exists a vertex $ v \in R $ such that $ d(e_1, v) \neq d(e_2, v) $, where $ d(e, v) $ is defined as $ d(e = uw, v) = \min\{ d(u, v), d(w, v) \} $. The edge metric dimension is defined as the number of elements in the smallest edge resolving set. Finding these dimensions is an NP-hard problem, making efficient computations precious. In this article, we explored the metric dimension, edge metric dimension, partition dimension and edge partition dimension of the heptagonal snake graph $ (HPS_k) $.

References

[1]	D. B. West, Introduction to graph theory, Upper Saddle River: Prentice Hall, 2001.
[2]	A. Prathik, K. Uma, J. Anuradha, An overview of application of graph theory, Int. J. ChemTech Res., 9 (2016), 242–248.
[3]	F. Harary, R. Z. Norman, Graph theory as a mathematical model in social science, 1953.
[4]	G. A. Pavlopoulos, M. Secrier, C. N. Moschopoulos, T. G. Soldatos, S. Kossida, J. Aerts, et al., Using graph theory to analyze biological networks, BioData Min., 4 (2011), 1–27. https://doi.org/10.1186/1756-0381-4-10 doi: 10.1186/1756-0381-4-10
[5]	R. P. Singh, Application of graph theory in computer science and engineering, Int. J. Comput. Appl., 104 (2014), 1.
[6]	D. H. Cai, P. Z. Fan, Q. Y. Zou, Y. Q. Xu, Z. G. Ding, Z. Q. Liu, Active device detection and performance analysis of massive non-orthogonal transmissions in cellular Internet of Things, Sci. China Inform. Sci., 65 (2022), 182301. https://doi.org/10.1007/s11432-021-3328-y doi: 10.1007/s11432-021-3328-y
[7]	S. H. Zheng, C. Shen, X. Chen, Design and analysis of uplink and downlink communications for federated learning, IEEE J. Sel. Areas Commun., 39 (2021), 2150–2167. https://doi.org/10.1109/JSAC.2020.3041388 doi: 10.1109/JSAC.2020.3041388
[8]	Y. H. Guo, R. Zhao, S. W. Lai, L. S. Fan, X. F. Lei, G. K. Karagiannidis, Distributed machine learning for multiuser mobile edge computing systems, IEEE J. Sel. Top. Signal Process., 16 (2022), 460–473. https://doi.org/10.1109/JSTSP.2022.3140660 doi: 10.1109/JSTSP.2022.3140660
[9]	C. Y. Tan, D. H. Cai, F. Fang, Z. G. Ding, P. Z. Fan, Federated unfolding learning for CSI feedback in distributed edge networks, IEEE Trans. Commun., 73 (2025), 410–424. https://doi.org/10.1109/TCOMM.2024.3429170 doi: 10.1109/TCOMM.2024.3429170
[10]	P. J. Slater, Leaves of trees, In: Proceeding of the 6th Southeastern Conference on Combinatorics, Graph Theory and Computing, 14 (1975), 549–559.
[11]	P. J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci., 22 (1988), 445–455.
[12]	F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combin., 2 (1976), 191–195.
[13]	Q. K. Meng, M. M. Polycarpo, Sensor selection for high-dimensional swarm systems based on observability analysis, In: 2023 31st Mediterranean Conference on Control and Automation (MED), 2023,967–973. https://doi.org/10.1109/MED59994.2023.10185854
[14]	A. Kelenc, N. Tratnik, 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 doi: 10.1016/j.dam.2018.05.052
[15]	D. J. Klein, E. Yi, A comparison on metric dimension of graphs, line graphs and line graphs of the subdivision graphs, Eur. J. Pure Appl. Math., 5 (2012), 302–316.
[16]	A. Ahmad, A. N. A. Koam, M. H. F. Siddiqui, M. Azeem, Resolvability of the starphene structure and applications in electronics, Ain Shams Eng. J., 13 (2022), 101587. https://doi.org/10.1016/j.asej.2021.09.014 doi: 10.1016/j.asej.2021.09.014
[17]	I. Tomescu, I. Javaid, On the metric dimension of the Jahangir graph, Bull. Math. Soc. Sci. Math. Roumanie, 50 (2007), 371–376.
[18]	S. K. Sharma, V. K. Bhat, Metric dimension of heptagonal circular ladder, Discrete Math. Algorithms Appl., 13 (2021), 2050095. https://doi.org/10.1142/S1793830920500950 doi: 10.1142/S1793830920500950
[19]	G. Chartrand, E. Salehi, P. Zhang, The partition dimension of a graph, Aequationes Math., 59 (2000), 45–54. https://doi.org/10.1007/PL00000127 doi: 10.1007/PL00000127
[20]	G. Chartrand, L. Eroh, M. A. Johnson, O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105 (2000), 99–113. https://doi.org/10.1016/S0166-218X(00)00198-0 doi: 10.1016/S0166-218X(00)00198-0
[21]	M. Hauptmann, R. Schmied, C. Viehmann, Approximation complexity of metric dimension problem, J. Discrete Algorithms, 14 (2012), 214–222. https://doi.org/10.1016/j.jda.2011.12.010 doi: 10.1016/j.jda.2011.12.010
[22]	P. Manuel, B. Rajan, I. Rajasingh, M. C. Monica, On minimum metric dimension of honeycomb networks, J. Discrete Algorithms, 6 (2008), 20–27. https://doi.org/10.1016/j.jda.2006.09.002 doi: 10.1016/j.jda.2006.09.002
[23]	S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math., 70 (1996), 217–229. https://doi.org/10.1016/0166-218X(95)00106-2 doi: 10.1016/0166-218X(95)00106-2
[24]	A. Sebő, E. Tannier, On metric generators of graphs, Math. Oper. Res., 29 (2004), 383–393. https://doi.org/10.1287/moor.1030.0070 doi: 10.1287/moor.1030.0070
[25]	S. Söderberg, H. S. Shapiro, A combinatory detection problem, Amer. Math. Monthly, 70 (1963), 1066–1070. https://doi.org/10.1080/00029890.1963.11992174 doi: 10.1080/00029890.1963.11992174
[26]	M. Perc, J. Gómez-Gardenes, A. Szolnoki, L. M. Floría, Y. Moreno, Evolutionary dynamics of group interactions on structured populations: a review, J. R. Soc. Interface, 10 (2013), 20120997. https://doi.org/10.1098/rsif.2012.0997 doi: 10.1098/rsif.2012.0997
[27]	M. Perc, A. Szolnoki, Coevolutionary games–a mini review, BioSystems, 99 (2010), 109–125. https://doi.org/10.1016/j.biosystems.2009.10.003 doi: 10.1016/j.biosystems.2009.10.003
[28]	J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, et al., On the metric dimension of cartesian products of graphs, SIAM J. Discrete Math., 21 (2007), 423–441. https://doi.org/10.1137/050641867 doi: 10.1137/050641867
[29]	Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihal'ak, Network discovery and verification, IEEE J. Sel. Areas Commun., 24 (2006), 2168–2181. https://doi.org/10.1109/JSAC.2006.884015 doi: 10.1109/JSAC.2006.884015
[30]	V. Chvátal, Mastermind, Combinatorica, 3 (1983), 325–329. https://doi.org/10.1007/BF02579188 doi: 10.1007/BF02579188
[31]	M. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Statist., 3 (1993), 203–236. https://doi.org/10.1080/10543409308835060 doi: 10.1080/10543409308835060
[32]	M. A. Johnson, Browsable structure-activity datasets, Adv. Mol. Similarity, 2 (1998), 153–170.
[33]	R. A. Melter, I. Tomescu, Metric bases in digital geometry, Comput. Vis. Graph. Image Process., 25 (1984), 113–121. https://doi.org/10.1016/0734-189X(84)90051-3 doi: 10.1016/0734-189X(84)90051-3
[34]	A. N. A. Koam, S. Ali, A. Ahmad, M. Azeem, M. K. Jamil, Resolving set and exchange property in nanotube, AIMS Math., 8 (2023), 20305–20323. https://doi.org/10.3934/math.20231035 doi: 10.3934/math.20231035
[35]	S. Imran, M. K. Siddique, M. Hussain, Computing the upper bounds for the metric dimension of cellulose network, Appl. Math., 19 (2019), 585–605.
[36]	A. Ahmad, M. Bača, S. Sultan, Computing the metric dimension of kayak paddle graph and cycles with chord, Proyecciones, 39 (2020), 287–300. http://dx.doi.org/10.22199/issn.0717-6279-2020-02-0018 doi: 10.22199/issn.0717-6279-2020-02-0018
[37]	M. Imran, H. M. A. Siddiqui, Computing the metric dimension of convex polytopes generated by wheel related graphs, Acta Math. Hungar., 149 (2016), 10–30. https://doi.org/10.1007/s10474-016-0606-1 doi: 10.1007/s10474-016-0606-1
[38]	A. F. Beardon, Resolving the hypercube, Discrete Appl. Math., 161 (2013), 1882–1887. https://doi.org/10.1016/j.dam.2013.02.012 doi: 10.1016/j.dam.2013.02.012
[39]	X. J. Zhang, M. Naeem, Metric dimension of crystal cubic carbon structure, J. Math., 2021 (2021), 3438611. https://doi.org/10.1155/2021/3438611 doi: 10.1155/2021/3438611
[40]	Z. Hussain, M. Munir, A. Ahmad, M. Chaudhary, J. A. Khan, I. Ahmed, Metric basis and metric dimension of 1-pentagonal carbon nanocone networks, Sci. Rep., 10 (2020), 19687. https://doi.org/10.1038/s41598-020-76516-1 doi: 10.1038/s41598-020-76516-1
[41]	M. K. Siddiqui, M. Imran, Computing the metric and partition dimension of H-Naphtalenic and VC5C7 nanotubes, J. Optoelectron. Adv. Mater., 17 (2015), 790–794.
[42]	M. Azeem, M. F. Nadeem, Metric-based resolvability of polycyclic aromatic hydrocarbons, Eur. Phys. J. Plus, 136 (2021), 1–14. https://doi.org/10.1140/epjp/s13360-021-01399-8 doi: 10.1140/epjp/s13360-021-01399-8
[43]	M. Ahsan, Z. Zahid, S. Zafar, A. Rafiq, M. S. Sindhu, M. Umar, Computing the edge metric dimension of convex polytopes related graphs, J. Math. Comput. Sci., 22 (2021), 174–188. https://doi.org/10.22436/jmcs.022.02.08 doi: 10.22436/jmcs.022.02.08
[44]	M. S. Bataineh, N. Siddiqui, Z. Raza, Edge metric dimension of $k$ multiwheel graph, Rocky Mountain J. Math., 50 (2020), 1175–1180. https://doi.org/10.1216/rmj.2020.50.1175 doi: 10.1216/rmj.2020.50.1175
[45]	R. Adawiyah, Dafik, R. Alfarisi, R. M. Prihandini, I. H. Agustin, Edge metric dimension on some families of tree, J. Phys. Conf. Ser., 1180 (2019), 012005. https://doi.org/10.1088/1742-6596/1180/1/012005 doi: 10.1088/1742-6596/1180/1/012005
[46]	V. Filipović, A. Kartelj, J. Kratica, Edge metric dimension of some generalized Petersen graphs, Results Math., 74 (2019), 1–15. https://doi.org/10.1007/s00025-019-1105-9 doi: 10.1007/s00025-019-1105-9
[47]	P. Singh, S. Sharma, S. K. Sharma, V. K. Bhat, Metric dimension and edge metric dimension of windmill graphs, AIMS Math., 6 (2021), 9138–9153. https://doi.org/10.3934/math.2021531 doi: 10.3934/math.2021531
[48]	B. Deng, M. F. Nadeem, M. Azeem, On the edge metric dimension of different families of Möbius networks, Math. Probl. Eng., 2021 (2021), 6623208. https://doi.org/10.1155/2021/6623208 doi: 10.1155/2021/6623208
[49]	S. Bukhari, M. K. Jamil, M. Azeem, S. Swaray, Patched network and its vertex-edge metric-based dimension, IEEE Access, 11 (2023), 4478–4485. https://doi.org/10.1109/ACCESS.2023.3235398 doi: 10.1109/ACCESS.2023.3235398
[50]	D. Kuziak, E. Maritz, T. Vetrìk, I. G. Yero, The edge partition dimension of graphs, Discrete Math. Lett., 12 (2023), 34–39. https://doi.org/10.47443/dml.2023.010 doi: 10.47443/dml.2023.010
[51]	F. Okamoto, B. Phinezy, P. Zhang, The local metric dimension of a graph, Math. Bohem., 135 (2010), 239–255. https://doi.org/10.21136/MB.2010.140702 doi: 10.21136/MB.2010.140702
[52]	R. Adawiyah, Dafik, R. Alfarisi, R. M. Prihandini, I. H. Agustin, M. Venkatachalam, The local edge metric dimension of graph, J. Phys. Conf. Ser., 1543 (2020), 012009. https://doi.org/10.1088/1742-6596/1543/1/012009 doi: 10.1088/1742-6596/1543/1/012009
[53]	L. Susilowati, I. Sa'adah, R. Z. Fauziyyah, A. Erfanian, Slamin, The dominant metric dimension of graphs, Heliyon, 6 (2020), e03633. https://doi.org/10.1016/j.heliyon.2020.e03633 doi: 10.1016/j.heliyon.2020.e03633
[54]	H. M. Ikhlaq, S. Hayat, H. M. A. Siddiqui, Unique identification and domination of edges in a graph: the vertex-edge dominant edge metric dimension, 2022, arXiv: 2211.09327.
[55]	R. Alfarisi, S. K. S. Husain, L. Susilowati, A. I. Kristiana, Dominant mixed metric dimension of graph, Stat. Optim. Inform. Comput., 12 (2024), 1826–1833. https://doi.org/10.19139/soic-2310-5070-1925 doi: 10.19139/soic-2310-5070-1925
[56]	R. Simanjuntak, P. Siagian, T. Vetrik, The multiset dimension of graphs, 2017, arXiv: 1711.00225.
[57]	R. Alfarisi, Y. Q. Lin, J. Ryan, D. Dafik, I. H. Agustin, A note on multiset dimension and local multiset dimension of graphs, Stat. Optim. Inform. Comput., 8 (2020), 890–901. https://doi.org/10.19139/soic-2310-5070-727 doi: 10.19139/soic-2310-5070-727
[58]	S. Arumugam, V. Mathew, The fractional metric dimension of graphs, Discrete Math., 312 (2012), 1584–1590. https://doi.org/10.1016/j.disc.2011.05.039 doi: 10.1016/j.disc.2011.05.039
[59]	H. Benish, M. Murtaza, I. Javaid, The fractional local metric dimension of graphs, 2018, arXiv: 1810.02882.
[60]	O. R. Oellermann, J. Peters-Fransen, The strong metric dimension of graphs and digraphs, Discrete Appl. Math., 155 (2007), 356–364. https://doi.org/10.1016/j.dam.2006.06.009 doi: 10.1016/j.dam.2006.06.009
[61]	C. X. Kang, E. Yi, The fractional strong metric dimension of graphs, In: Combinatorial Optimization and Applications, Cham: Springer, 2013, 84–95. https://doi.org/10.1007/978-3-319-03780-6_8

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)