Computing the edge metric dimension of convex polytopes related graphs
-
1193
Downloads
-
2559
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
ISRP Style
Muhammad Ahsan, Zohaib Zahid, Sohail Zafar, Arif Rafiq, Muhammad Sarwar Sindhu, Muhammad Umar, Computing the edge metric dimension of convex polytopes related graphs, Journal of Mathematics and Computer Science, 22 (2021), no. 2, 174--188
AMA Style
Ahsan Muhammad, Zahid Zohaib, Zafar Sohail, Rafiq Arif, Sindhu Muhammad Sarwar, Umar Muhammad, Computing the edge metric dimension of convex polytopes related graphs. J Math Comput SCI-JM. (2021); 22(2):174--188
Chicago/Turabian Style
Ahsan, Muhammad, Zahid, Zohaib, Zafar, Sohail, Rafiq, Arif, Sindhu, Muhammad Sarwar, Umar, Muhammad. "Computing the edge metric dimension of convex polytopes related graphs." Journal of Mathematics and Computer Science, 22, no. 2 (2021): 174--188
Keywords
- Edge metric dimension
- edge metric generator
- edge metric basis
- resolving set
- prism related graphs
- flower graph
MSC
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), (),
-
[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
-
[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
-
[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
-
[5]
G. Chartrand, C. Poisson, P. Zhang, Resolvability and the upper dimension of graphs, Comput. Math. Appl., 39 (2000), 19--28
-
[6]
G. Chartrand, P. Zhang, The theory and applications of resolvability in graphs: a survey, Congr. Numer., 160 (2003), 47--68
-
[7]
V. Filipović, A. Kartelj, J. Kratica, , Edge Metric Dimension of Some Generalized Petersen Graphs, Results Math., 74 (2019), 15 pages
-
[8]
I. Gutman, L. Pavlovic, More on distance of line graphs, Graph Theory Notes New York, 33 (1997), 14--18
-
[9]
M. Hallaway, C. X. Kang, E. Yi, On metric dimension of permutation graphs, J. Comb. Optim., 28 (2014), 814--826
-
[10]
F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combin., 2 (1976), 191--195
-
[11]
M. Imran, A. Q. Baig, A. Ahmad, Families of plane graphs with constant metric dimension, Util. Math., 88 (2012), 43--57
-
[12]
M. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Stat., 3 (1993), 203--236
-
[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
-
[14]
S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math., 70 (1996), 217--229
-
[15]
R. A. Melter, I. Tomescu, Metric bases in digital geometry, Comput. Vision Graphics Image Process., 25 (1984), 113--121
-
[16]
I. Peterin, I. G. Yero, Edge metric dimension of some graph operations, Bull. Malays. Math. Sci. Soc., 43 (2020), 2465--2477
-
[17]
A.Sebő, E. Tannier, On metric generators of graphs, Math. Oper. Res., 29 (2004), 383--393
-
[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
-
[19]
P. J. Slater, Dominating and reference sets in graphs, J. Math. Phys. Sci., 22 (1988), 445--455
-
[20]
S. Sultan, On the Metric Dimension and Minimal Doubly Resolving Sets of Families of Graphs, Ph.D. Thesis (G. C. University), Lahore (2018)
-
[21]
I. Tomescu, M. Imran, R-sets and metric dimension of necklace graphs, Appl. Math. Inf. Sci., 9 (2015), 63--67
-
[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
-
[23]
N. Zubrilina, On the edge dimension of a graph, Discrete Math., 341 (2018), 2083--2088