The cactus graph has many practical applications, particularly in radio communication systems. Let $ G = (V, E) $ be a finite, undirected, and simple connected graph, then the edge metric dimension of $ G $ is the minimum cardinality of the edge metric generator for $ G $ (an ordered set of vertices that uniquely determines each pair of distinct edges in terms of distance vectors). Given an ordered set of vertices $ \mathcal{G}_e = \{g_1, g_2, ..., g_k \} $ of a connected graph $ G $, for any edge $ e\in E $, we referred to the $ k $-vector (ordered $ k $-tuple), $ r(e|\mathcal{G}_e) = (d(e, g_1), d(e, g_2), ..., d(e, g_k)) $ as the edge metric representation of $ e $ with respect to $ G_e $. In this regard, $ \mathcal{G}_e $ is an edge metric generator for $ G $ if, and only if, for every pair of distinct edges $ e_1, e_2 \in E $ implies $ r (e_1 |\mathcal{G}_e) \neq r (e_2 |\mathcal{G}_e) $. In this paper, we investigated another class of cacti different from the cacti studied in previous literature. We determined the edge metric dimension of the following cacti: $ \mathfrak{C}(n, c, r) $ and $ \mathfrak{C}(n, m, c, r) $ in terms of the number of cycles $ (c) $ and the number of paths $ (r) $.
Citation: Lyimo Sygbert Mhagama, Muhammad Faisal Nadeem, Mohamad Nazri Husin. On the edge metric dimension of some classes of cacti[J]. AIMS Mathematics, 2024, 9(6): 16422-16435. doi: 10.3934/math.2024795
The cactus graph has many practical applications, particularly in radio communication systems. Let $ G = (V, E) $ be a finite, undirected, and simple connected graph, then the edge metric dimension of $ G $ is the minimum cardinality of the edge metric generator for $ G $ (an ordered set of vertices that uniquely determines each pair of distinct edges in terms of distance vectors). Given an ordered set of vertices $ \mathcal{G}_e = \{g_1, g_2, ..., g_k \} $ of a connected graph $ G $, for any edge $ e\in E $, we referred to the $ k $-vector (ordered $ k $-tuple), $ r(e|\mathcal{G}_e) = (d(e, g_1), d(e, g_2), ..., d(e, g_k)) $ as the edge metric representation of $ e $ with respect to $ G_e $. In this regard, $ \mathcal{G}_e $ is an edge metric generator for $ G $ if, and only if, for every pair of distinct edges $ e_1, e_2 \in E $ implies $ r (e_1 |\mathcal{G}_e) \neq r (e_2 |\mathcal{G}_e) $. In this paper, we investigated another class of cacti different from the cacti studied in previous literature. We determined the edge metric dimension of the following cacti: $ \mathfrak{C}(n, c, r) $ and $ \mathfrak{C}(n, m, c, r) $ in terms of the number of cycles $ (c) $ and the number of paths $ (r) $.
[1] | S. Khuller, B. Raghavachari, A. Rosenfeld, Localization in graphs, Digital Repository at the University of Maryland, 1994. |
[2] | G. Chartrand, L. Eroh, M. Johnson, O. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discret. Appl. Math., 105 (2000), 99–113. https://doi.org/10.1016/S0166-218X(00)00198-0 doi: 10.1016/S0166-218X(00)00198-0 |
[3] | J. Hu, X. Shang, Detection of network motif based on a novel graph canonization algorithm from transcriptional regulation networks, Molecules, 22 (2017), 2194. https://doi.org/10.3390/molecules22122194 doi: 10.3390/molecules22122194 |
[4] | B. Spinelli, L. E. Celis, P. Thiran, Observer placement for source localization: The effect of budgets and transmission variance, In 54th Annual Allerton Conference on Communication, Control, and Computing, 2016. |
[5] | R. C. Tillquist, 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 doi: 10.1007/s00285-019-01348-1 |
[6] | P. J. Slater, Leaves of trees, Congr. Numer., 14 (1975), 549–559. |
[7] | F. Harary, R. A. Melter, On the metric dimension of graph, Ars Combinatoria, 2 (1976), 191–195. |
[8] | A. Kelenc, N. Tratnik, I. G. Yero, Uniquely identifying the edges of a graph: The edge metric dimension, Discret. Appl. Math., 251 (2018), 204–220. https://doi.org/10.1016/j.dam.2018.05.052 doi: 10.1016/j.dam.2018.05.052 |
[9] | T. Iqbal, M. N. Azhar, S. A. Ul Haq Bokhary, The K-size edge metric dimension of graphs, J. Math., 2020 (2020). https://doi.org/10.1155/2020/1023175 |
[10] | V. Filipović, A. Kartelj, J. Kratica, Edge metric dimension of some generalized Petersen graphs, Results Math., 74 (2019). https://doi.org/10.1007/s00025-019-1105-9 |
[11] | H. Raza, Y. Ji, Computing the mixed metric dimension of a generalized Petersen graph P(n, 2), Front. Phys., 2020. http://dx.doi.org/10.3389/fphy.2020.00211 |
[12] | T. Iqbal, M. Rafiq, M. N. Azhar, M. Salman, I. Khalid, On the edge resolvability of double generalized Petersen graphs, J. Math., 2022. http://dx.doi.org/10.1155/2022/6490698 |
[13] | J. Geneson, Metric dimension and pattern avoidance in graphs, Discret. Appl. Math., 2020. http://dx.doi.org/10.1016/j.dam2020.03.001. |
[14] | N. Goshi, S. Zafar, T. Rashid, Fractional local edge dimensions of a graph, Discret. Math. Algorit., 2023. http://dx.doi.org/10.1142/S1793830923500246 |
[15] | J. Geneson, S. Kaustav, A. Labelle, Extremal results for graphs of bounded metric dimension, Discret. Appl. Math., 2022. http://dx.doi.org/10.1016/j.dam2021.11.015. |
[16] | N. Zubrilina, On the edge dimension of a graph, Discrete Math., 341 (2018), 2083–2088. http://dx.doi.org/10.1016/j.disc.2018.04.010 doi: 10.1016/j.disc.2018.04.010 |
[17] | I. Peterin, I. G. Yero, Edge metric dimension of some graph operations, B. Malaysian Math. Sci. Soc., 43 (2020), 2465–2477. http://dx.doi.org/10.1007/s40840-019-00816-7 doi: 10.1007/s40840-019-00816-7 |
[18] | Y. Zhang, S. Gao, On the edge metric dimension of convex polytopes and its related graphs, J. Comb. Optim., 2020. http://dx.doi.org/10.1007/s10878-019-00472-4 |
[19] | H. M. A. Siddiqui, A. Mujahid, M. A. Binyamin, M. F. Nadeem, On certain bounds for edge metric dimension of Zero-Divisor graphs associated with rings, Math. Probl. Eng., 2021 (2021). http://dx.doi.org/10.1155/2021/5826722 |
[20] | M. Wei, J. Yue, X. Zhu, On the edge metric dimension of graphs, AIMS Math., 5 (2020), 4459–4465. http://dx.doi.org/10.3934/math.2020286 doi: 10.3934/math.2020286 |
[21] | E. Zhu, A. Taranenko, Z. Shao, J. Xu, On graphs with the maximum edge metric dimension, Discret. Appl. Math., 257 (2019), 317–324. http://dx.doi.org/10.1016/j.dam.2018.08.031 doi: 10.1016/j.dam.2018.08.031 |
[22] | R. Adawiyah, R. Alfarisi, R. M. Prihandini, I. H. Agustin, Edge metric dimension on some families of tree, In: Journal of Physics: Conference Series, Institute of Physics Publishing, 2019. http://dx.doi.org/10.1088/1742-6596/1180/1/012005 |
[23] | B. Deng, M. F. Nadeem, M. Azeem, On the edge metric dimension of different families of möbius networks, Math. Probl. Eng., 2021 (2021). http://dx.doi.org/10.1155/2021/6623208 |
[24] | M. Knor, S. Majstorović, A. T. M. Toshi, R. Škrekovski, I. G. Yero, Graphs with the edge metric dimension smaller than the metric dimension, Appl. Math. Comput., 401 (2021). http://dx.doi.org/10.1016/j.amc.2021.126076 |
[25] | J. Sedlar, R. Škrekovski, Vertex and edge metric dimensions of cacti, Discret. Appl. Math., 320 (2022), 126–139. http://dx.doi.org/10.1016/j.dam.2022.05.008 doi: 10.1016/j.dam.2022.05.008 |
[26] | H. M. Ikhlaq, H. M. A. Siddiqui, M. Imran, A comparative study of three resolving parameters of graphs, Complexity, 2021 (2021). http://dx.doi.org/10.1155/2021/1927181 |
[27] | E. Zhu, S. Peng, C. Liu, Identifying the exact value of the metric dimension and edge dimension of unicyclic graphs, Mathematics, 10 (2022), 1–14. http://dx.doi.org/10.3390/math10193539 doi: 10.3390/math10193539 |
[28] | E. Zhu, S. Peng, C. Liu, Metric dimension and edge metric dimension of unicyclic graphs, arXiv Preprint, 2021. |
[29] | M. Knor, J. Sedlar, R. Škrekovski, Remarks on the vertex and the edge metric dimension of 2-connected graphs, Mathematics, 10 (2022), 1–19. http://dx.doi.org/10.3390/math10142411 doi: 10.3390/math10142411 |
[30] | J. Sedlar, R. Škrekovski, Metric dimensions vs. cyclomatic number of graphs with minimum degree at least two, Appl. Math. Comput., 427 (2022), 1–19. http://dx.doi.org/10.1016/j.amc.2022.127147 doi: 10.1016/j.amc.2022.127147 |
[31] | J. Sedlar, R. Škrekovski, Bounds on metric dimensions of graphs with edge disjoint cycles, Appl. Math. Comput., 396 (2021), 125908. http://dx.doi.org/10.1016/j.amc.2020.125908 doi: 10.1016/j.amc.2020.125908 |
[32] | M. Rafiullah, H. M. A. Siddiqui, S. Ahmad, Resolvability of some convex polytopes, Util. Math., 111 (2019). |
[33] | M. Ahsan, Z. Zahid, S. Zafar, Edge metric dimension of some classes of circulant graphs, An. Stiint. U. Al. I.-Mat., 28 (2020), 15–37. http://dx.doi.org/10.2478/auom-2020-0032 doi: 10.2478/auom-2020-0032 |
[34] | F. Yasmeen, S. Akhter, K. Ali, S. T. R. Rizvi, Edge Mostar indices of cacti graph with fixed cycles, Front. Chem., 9 (2021), 1–7. http://dx.doi.org/10.3389/fchem.2021.693885 doi: 10.3389/fchem.2021.693885 |
[35] | S. Chen, Cacti with the smallest, second smallest, and third smallest Gutman index, J. Comb. Optim., 31 (2016), 327–332. http://dx.doi.org/10.1007/s10878-014-9743-z doi: 10.1007/s10878-014-9743-z |
[36] | S. Li, H. Yang, Q. Zhao, Sharp bounds on Zagreb indices of cacti with k pendant vertices, Filomat, 26 (2012), 1189–1200. http://dx.doi.org/10.2298/FIL1206189L doi: 10.2298/FIL1206189L |
[37] | S. Wang, On extremal cacti with respect to the Szeged index, Appl. Math. Comput., 309 (2017), 85–92. http://dx.doi.org/10.1016/j.amc.2017.03.036 doi: 10.1016/j.amc.2017.03.036 |
[38] | M. F. Nadeem, W. Ali, H. M. A. Siddiqui, Locating number of biswapped networks, Int. J. Found. Comput. S., 33 (2022), 667–690. http://dx.doi.org/10.1142/S0129054122420096 doi: 10.1142/S0129054122420096 |