Research article

Fault-tolerant edge metric dimension of certain families of graphs

  • Received: 23 July 2020 Accepted: 16 October 2020 Published: 11 November 2020
  • MSC : 68R01, 68R05, 68R10

  • Let $W_E = \{w_1, w_2, \ldots, w_k\}$ be an ordered set of vertices of graph $G$ and let $e$ be an edge of $G$. Suppose $d(x, e)$ denotes distance between edge $e$ and vertex $x$ of $G$, defined as $d(e, x) = d(x, e) = \min \{d(x, a), d(x, b)\}$, where $e = ab$. A vertex $x$ distinguishes two edges $e_1$ and $e_2$, if $d(e_1, x)\neq d(e_2, x)$. The representation $r(e\mid W_E)$ of $e$ with respect to $W_E$ is the k-tuple $(d(e, w_1), d(e, w_2), \ldots, d(e, w_k))$. If distinct edges of $G$ have distinct representation with respect to $W_E$, then $W_E$ is called edge metric generator for $G$. An edge metric generator of minimum cardinality is an edge metric basis for $G$, and its cardinality is called edge metric dimension of $G$, denoted by $(G)$. In this paper, we initiate the study of fault-tolerant edge metric dimension. Let $\acute{W}_E$ be edge metric generator of graph $G$, then $\acute{W}_E$ is called fault-tolerant edge metric generator of $G$ if $\acute{W}_E \setminus \{v \}$ is also an edge metric generator of graph $G$ for every $v \in \acute{W}_E$. A fault-tolerant edge metric generator of minimum cardinality is a fault-tolerant edge metric basis for graph $G$, and its cardinality is called fault-tolerant edge metric dimension of $G$. We also computed the fault-tolerant edge metric dimension of path, cycle, complete graph, cycle with chord graph, tadpole graph and kayak paddle graph.

    Citation: Xiaogang Liu, Muhammad Ahsan, Zohaib Zahid, Shuili Ren. Fault-tolerant edge metric dimension of certain families of graphs[J]. AIMS Mathematics, 2021, 6(2): 1140-1152. doi: 10.3934/math.2021069

    Related Papers:

  • Let $W_E = \{w_1, w_2, \ldots, w_k\}$ be an ordered set of vertices of graph $G$ and let $e$ be an edge of $G$. Suppose $d(x, e)$ denotes distance between edge $e$ and vertex $x$ of $G$, defined as $d(e, x) = d(x, e) = \min \{d(x, a), d(x, b)\}$, where $e = ab$. A vertex $x$ distinguishes two edges $e_1$ and $e_2$, if $d(e_1, x)\neq d(e_2, x)$. The representation $r(e\mid W_E)$ of $e$ with respect to $W_E$ is the k-tuple $(d(e, w_1), d(e, w_2), \ldots, d(e, w_k))$. If distinct edges of $G$ have distinct representation with respect to $W_E$, then $W_E$ is called edge metric generator for $G$. An edge metric generator of minimum cardinality is an edge metric basis for $G$, and its cardinality is called edge metric dimension of $G$, denoted by $(G)$. In this paper, we initiate the study of fault-tolerant edge metric dimension. Let $\acute{W}_E$ be edge metric generator of graph $G$, then $\acute{W}_E$ is called fault-tolerant edge metric generator of $G$ if $\acute{W}_E \setminus \{v \}$ is also an edge metric generator of graph $G$ for every $v \in \acute{W}_E$. A fault-tolerant edge metric generator of minimum cardinality is a fault-tolerant edge metric basis for graph $G$, and its cardinality is called fault-tolerant edge metric dimension of $G$. We also computed the fault-tolerant edge metric dimension of path, cycle, complete graph, cycle with chord graph, tadpole graph and kayak paddle graph.


    加载中


    [1] P. J. Slater, Leaves of trees, Congr. Numer., 14 (1975), 549-559.
    [2] M. C. Hernando, M. Mora, P. J. Slater, D. R. Wood, Fault-tolerant metric dimension of graphs, Convexity Discrete Struct., 5 (2008), 81-85.
    [3] 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. doi: 10.1016/j.dam.2018.05.052
    [4] A. Tabassum, M. A. Umar, M. Perveen, A. Raheem, Antimagicness of subdivided fans, Open J. Math. Sci., 4 (2020), 18-22. doi: 10.30538/oms2020.0089
    [5] J. B. Liu, Z. Zahid, Z. Nasir, W. Nazeer, Edge version of metric dimension and doubly resolving sets of the necklace graph, Mathematics, 6 (2018), 243. doi: 10.3390/math6110243
    [6] H. F. M. Salih, S. M. Mershkhan, Generalized the Liouville's and Mobius functions of graph, Open J. Math. Sci., 4 (2020), 186-194. doi: 10.30538/oms2020.0109
    [7] W. Gao, B. Muzaffar, W. Nazeer, K-Banhatti and K-hyper Banhatti indices of dominating David derived network, Open J. Math. Anal., 1 (2017), 13-24.
    [8] N. Zubrilina, On the edge dimension of a graph, Discrete Math., 341 (2018), 2083-2088. doi: 10.1016/j.disc.2018.04.010
    [9] F. Haray, R. A. Melter, On the metric dimension of a graph, Ars Comb., 2 (1976), 191-195.
    [10] G. Chartrand, L. Eroh, M. A. Johnson, O. R. Oeller-mann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105 (2000), 99-113.
    [11] G. Chartrand, C. Poisson, P. Zhang, Resolvability and the upper dimension of graphs, Comput. Math. Appl., 39 (2000), 19-28.
    [12] M. Imran, A. Q. Baig, A. Ahmad, Families of plane graphs with constant metric dimension, Utilitas Math., 88 (2012), 43-57.
    [13] M. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Stat., 3 (1993), 203-236. doi: 10.1080/10543409308835060
    [14] S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math., 70 (1996), 217-229. doi: 10.1016/0166-218X(95)00106-2
    [15] R. A. Melter, I. Tomescu, Metric bases in digital geometry, Comput. Vision, Graphics, Image Process., 28 (1984), 113-121.
    [16] J. Caceres, 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 (2008), 423-441.
    [17] J. Kratica, V. Filipovii, A. Kartelj, Edge metric dimension of some generalized Petersen graphs, 2018. Available from: http://arXiv.org/abs/1807.00580v1.
    [18] 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. Computer Sci., 22 (2021), 174-188.
    [19] U. Ali, Y. Ahmad, M. S. Sardar, On 3-total edge product cordial labeling of tadpole, book and flower graphs, Open J. Math. Sci., 4 (2020), 48-55. doi: 10.30538/oms2020.0093
    [20] S. M. Kang, M. A. Zahid, W. Nazeer, W. Gao, Calculating the degree-based topological indices of dendrimers, Open Chem., 16 (2018), 681-688. doi: 10.1515/chem-2018-0071
    [21] Y. C. Kwun, A. U. R. Virk, W. Nazeer, M. A. Rehman, S. M. Kang, On the multiplicative degreebased topological indices of silicon-carbon Si2C3-I [p, q] and Si2C3-II [p, q], Symmetry, 10 (2018), 320. doi: 10.3390/sym10080320
    [22] R. V. Voronov, The fault-tolerant metric dimension of the king's graph, Vestnik Saint Petersburg Univ. Appl. Math., Comput. Sci. Control Processes, 13 (2017), 241-249. doi: 10.21638/11701/spbu10.2017.302
    [23] H. Raza, S. Hayat, X. F. Pan, On the fault-tolerant metric dimension of convex polytopes, Appl. Math. Comput., 339 (2018), 172-185.
    [24] J. B. Liu, M. Munir, I. Ali, Z. Hussain, A. Ahmed, Fault-Tolerant metric dimension of Wheel related graphs, 2019. Available from: https://hal.archives-ouvertes.fr/hal-01857316v2.
    [25] M. Basak, L. Saha, G. K. Das, K. Tiwary, Fault-tolerant metric dimension of circulant graphs Cn(1, 2, 3), Theor. Comput. Sci., 2019. DOI: 10.1016/j.tcs.2019.01.011.
    [26] A. Shabbir, T. Zamfirescu, Fault-tolerant designs in triangular lattice networks, Appl. Anal., 10 (2016), 447-456.
    [27] W. Nazeer, A. Farooq, M. Younas, M. Munir, S. M. Kang, On molecular descriptors of carbon nanocones, Biomolecules, 8 (2018), 92. doi: 10.3390/biom8030092
    [28] Y. C. Kwun, M. Munir, W. Nazeer, S. Rafique, S. M. Kang, Computational analysis of topological indices of two Boron Nanotubes, Sci. Rep., 8 (2018), 1-14. doi: 10.1038/s41598-017-17765-5
    [29] M. Ahsan, S. Zafar, Edge metric dimension of certain families of graphs, Utilitas Math., In Press.
  • Reader Comments
  • © 2021 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(3912) PDF downloads(203) Cited by(18)

Article outline

Figures and Tables

Figures(5)  /  Tables(1)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog