Research article

On the edge metric dimension of some classes of cacti

  • Received: 07 March 2024 Revised: 21 April 2024 Accepted: 24 April 2024 Published: 10 May 2024
  • MSC : 97H50, 70G65, 14J15

  • 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

    Related Papers:

  • 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
  • Reader Comments
  • © 2024 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(531) PDF downloads(41) Cited by(0)

Article outline

Figures and Tables

Figures(2)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog