On metric dimension of plane graphs $\mathfrak{J}_{n}$, $\mathfrak{K}_{n}$ and $\mathfrak{L}_{n}$
DOI:
https://doi.org/10.13069/jacodesmath.1000842Keywords:
Resolving set, Metric basis, Independent set, Metric dimension, Planar graphAbstract
Let $\Gamma=\Gamma(\mathbb{V},\mathbb{E})$ be a simple (i.e., multiple edges and loops and are not allowed), connected (i.e., there exists a path between every pair of vertices), and an undirected (i.e., all the edges are bidirectional) graph. Let $d_{\Gamma}(\varrho_{i},\varrho_{j})$ denotes the geodesic distance between two nodes $\varrho_{i},\varrho_{j} \in \mathbb{V}$. The problem of characterizing the classes of plane graphs with constant metric dimensions is of great interest nowadays. In this article, we characterize three classes of plane graphs (viz., $\mathfrak{J}_{n}$, $\mathfrak{K}_{n}$, and $\mathfrak{L}_{n}$) which are generated by taking n-copies of the complete bipartite graph (or a star) $K_{1,5}$, and all of these plane graphs are radially symmetrical with the constant metric dimension. We show that three vertices is a minimal requirement for the unique identification of all vertices of these three classes of plane graphs.
Received: 30 September 2020 | Accepted: 20 May 2021Downloads
References
Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihal'ák, and L. S. Ram, Network discovery and verification, IEEE J. Sel. Areas Commun. 24(12) (2006) 2168–2181.
L. M. Blumenthal, Theory and Applications of Distance Geometry, Oxford University Press, Oxford (1953).
P. S. Buczkowski, G. Chartrand, C. Poisson, and P. Zhang, On $k$-dimensional graphs and their bases, Period. Math. Hungar. 46(1) (2003) 9–15.
J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, and D. R. Wood, On the metric dimension of some families of graphs, Electron. Notes Discrete Math. 22 (2005) 129–133.
G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105(1-3) (2000) 99–113.
F. Harary and R. A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195.
I. Javaid, M. T. Rahim, and K. Ali, Families of regular graphs with constant metric dimension, Utilitas Math. 75 (2008) 21–34.
S. Khuller, B. Raghavachari, and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70(3) (1996) 217–229.
R. A. Melter and I. Tomescu, Metric bases in digital geometry, Comput. Vision Graph. Image Process. 25(1) (1984) 113–121.
A. Sebő and E. Tannier, On metric generators of graphs, Math. Oper. Res. 29(2) (2004) 383–393.
P. J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.
I. Tomescu and M. Imran, Metric dimension and $R$-sets of a connected graph, Graphs Combin. 27(4) (2011) 585–591.
I. Tomescu and I. Javaid, On the metric dimension of the Jahangir graph, Bull. Math. Soc. Sci. Math. Roumanie (N.S.) 50(98)(4) (2007) 371–376.
