On metric dimension of plane graphs $\mathfrak{J}_{n}$, $\mathfrak{K}_{n}$ and $\mathfrak{L}_{n}$

Abstract

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.

Keywords

• Resolving set
• Metric basis
• Independent set
• Metric dimension
• Planar graph

References

1. [1] Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffman, M. Mihalak, L. S. Ram, Network discovery and verification, IEEE J. Sel. Areas Commun. 24 (2006) 2168–2181.
2. [2] L. M. Blumenthal, Theory and applications of distance geometry, Oxford: At the Clarendon Press (Geoffrey Cumberlege) (1953).
3. [3] P. S. Buczkowski, G. Chartrand, C. Poisson, P. Zhang, On k-dimensional graphs and their bases, Period. Math. Hung. 46(1) (2003) 9-15.
4. [4] J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, D. R. Wood, On the metric dimension of some families of graphs, Electron. Notes Discret. Math. 22 (2005) 129–133.
5. [5] 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.
6. [6] F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Comb. 2 (1976) 191-195.
7. [7] I. Javaid, M. T. Rahim, K. Ali, Families of regular graphs with constant metric dimension, Util. Math. 75 (2008) 21-34.
8. [8] S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217-229.

9. [9] R. A. Melter, I. Tomescu, Metric bases in digital geometry, Comput. Gr. Image Process. 25 (1984) 113-121.
10. [10] A. Sebo, E. Tannier, On metric generators of graphs, Math. Oper. Res. 29(2) (2004) 383–393.
11. [11] P. J. Slater, Leaves of trees, Congr. Numer 14 (1975) 549-559.
12. [12] I. Tomescu, M. Imran, Metric dimension and R-sets of a connected graph, Graphs Comb. 27 (2011) 585-591.
13. [13] I. Tomescu, I. Javaid, On the metric dimension of the Jahangir graph, Bull. Math. Soc. Sci. Math. Roumanie 50(98) (2007) 371-376.