Computing the edge metric dimension of convex polytopes related graphs

Volume 22, Issue 2, pp 174--188 http://dx.doi.org/10.22436/jmcs.022.02.08

Publication Date: July 31, 2020 Submission Date: May 17, 2020 Revision Date: June 03, 2020 Accteptance Date: June 16, 2020

Download PDF

Download XML

• Export citations
  • CITATIONS & REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • ARTICLE CITATION
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)

• 1190 Downloads
• 2551 Views

Authors

Muhammad Ahsan - Department of Mathematics, University of Management and Technology, Lahore 54770, Pakistan. Zohaib Zahid - Department of Mathematics, University of Management and Technology, Lahore 54770, Pakistan. Sohail Zafar - Department of Mathematics, University of Management and Technology, Lahore 54770, Pakistan. Arif Rafiq - Department of Mathematics, Virtual University of Pakistan (VU), Lahore, Pakistan. Muhammad Sarwar Sindhu - Department of Mathematics, Virtual University of Pakistan (VU), Lahore, Pakistan. Muhammad Umar - Department of Mathematics, Virtual University of Pakistan (VU), Lahore, Pakistan.

Abstract

Let \(G=(V(G),E(G))\) be a connected graph and \(d(f,y)\) denotes the distance between edge \(f\) and vertex \(y\), which is defined as \(d(f,y) = \min \{d(p,y),d(q,y)\}\), where \(f=pq\). A subset \(W_E \subseteq V(G)\) is called an edge metric generator for graph \(G\) if for every two distinct edges \(f_1, f_2 \in E(G)\), there exists a vertex \(y\in W_E\) such that \(d(f_1,y) \neq d(f_2,y)\). An edge metric generator with minimum number of vertices is called an edge metric basis for graph \(G\) and the cardinality of an edge metric basis is called the edge metric dimension represented by \(edim(G)\). In this paper, we study the edge metric dimension of flower graph \({f}_{n\times 3}\) and also calculate the edge metric dimension of the prism related graphs \(D_{n}^{'}\) and \(D_{n}^{t}\). It has been concluded that the edge metric dimension of \(D_{n}^{'}\) is bounded, while of \({f}_{n\times 3}\) and \(D_{n}^{t}\) is unbounded.

Share and Cite

Keywords

• Edge metric dimension
• edge metric generator
• edge metric basis
• resolving set
• prism related graphs
• flower graph

MSC

•  05C12
•  05C25

References

• [1] M. Ahsan, Z. Zahid, S. Zafar, Edge metric dimension of some classes of circulant graphs, Analele Stiintifice ale Universitatii Ovidius Constanta (in press), (),
  • View Article


• [2] M. Ali, G. Ali, U. Ali, M. T. Rahim, On cycle related graphs with constant metric dimension, Open J. Discrete Math., 2 (2012), 21--23
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [3] J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, D. R. Wood, On the metric dimension of cartesian products of graphs, SIAM J. Discrete Math., 21 (2007), 423--441
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [4] 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
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [5] G. Chartrand, C. Poisson, P. Zhang, Resolvability and the upper dimension of graphs, Comput. Math. Appl., 39 (2000), 19--28
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [6] G. Chartrand, P. Zhang, The theory and applications of resolvability in graphs: a survey, Congr. Numer., 160 (2003), 47--68
  • MathSciNet
  • Google Scholar
  • MATH


• [7] V. Filipović, A. Kartelj, J. Kratica, , Edge Metric Dimension of Some Generalized Petersen Graphs, Results Math., 74 (2019), 15 pages
  • View Article
  • Google Scholar
  • MATH


• [8] I. Gutman, L. Pavlovic, More on distance of line graphs, Graph Theory Notes New York, 33 (1997), 14--18
  • MathSciNet
  • Google Scholar


• [9] M. Hallaway, C. X. Kang, E. Yi, On metric dimension of permutation graphs, J. Comb. Optim., 28 (2014), 814--826
  • View Article
  • Google Scholar
  • MATH


• [10] F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combin., 2 (1976), 191--195
  • MathSciNet
  • Google Scholar
  • MATH


• [11] M. Imran, A. Q. Baig, A. Ahmad, Families of plane graphs with constant metric dimension, Util. Math., 88 (2012), 43--57
  • MathSciNet
  • Google Scholar
  • MATH


• [12] M. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Stat., 3 (1993), 203--236
  • View Article
  • Google Scholar
  • MATH


• [13] 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
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [14] S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math., 70 (1996), 217--229
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [15] R. A. Melter, I. Tomescu, Metric bases in digital geometry, Comput. Vision Graphics Image Process., 25 (1984), 113--121
  • View Article
  • Google Scholar
  • MATH


• [16] I. Peterin, I. G. Yero, Edge metric dimension of some graph operations, Bull. Malays. Math. Sci. Soc., 43 (2020), 2465--2477
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [17] A.Sebő, E. Tannier, On metric generators of graphs, Math. Oper. Res., 29 (2004), 383--393
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [18] P. J. Slater, Leaves of trees, Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton), 1975 (1975), 549--559
  • Google Scholar
  • MATH


• [19] P. J. Slater, Dominating and reference sets in graphs, J. Math. Phys. Sci., 22 (1988), 445--455
  • MathSciNet
  • Google Scholar


• [20] S. Sultan, On the Metric Dimension and Minimal Doubly Resolving Sets of Families of Graphs, Ph.D. Thesis (G. C. University), Lahore (2018)
  • View Article
  • Google Scholar


• [21] I. Tomescu, M. Imran, R-sets and metric dimension of necklace graphs, Appl. Math. Inf. Sci., 9 (2015), 63--67
  • View Article
  • MathSciNet
  • Google Scholar


• [22] Y. Z. Zhang, S. G. Gao, On the edge metric dimension of convex polytopes and its related graphs, J. Comb. Optim., 39 (2020), 334--350
  • View Article
  • Google Scholar
  • MATH


• [23] N. Zubrilina, On the edge dimension of a graph, Discrete Math., 341 (2018), 2083--2088
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH