We show that three vertices is a minimal requirement for the unique identification of all vertices of these three classes of plane graphs.
📌 3 Key Takeaways
🎯
Objective & Hypothesis: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.
📊
Key Findings & Data: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.
💡
Conclusion & Impact:We show that three vertices is a minimal requirement for the unique identification of all vertices of these three classes of plane graphs.
🔬Design:Research Article
📍Scope:Comprehensive Sample
⚙️Variables:Resolving set · Metric basis · Independent set
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.
SHARMA, S. K., SHARMA, S. K. (2021). On metric dimension of plane graphs $\mathfrak{J}_{n}$, $\mathfrak{K}_{n}$ and $\mathfrak{L}_{n}$. Journal of Algebra Combinatorics Discrete Structures and Applications, Cilt: 8 - Sayı: 3, 197–212. https://ajindex.com/articles/861493
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
L. M. Blumenthal, Theory and applications of distance geometry, Oxford: At the Clarendon Press (Geoffrey Cumberlege) (1953)
P. S. Buczkowski, G. Chartrand, C. Poisson, P. Zhang, On k-dimensional graphs and their bases, Period. Math. Hung. 46(1) (2003) 9-15
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
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
F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Comb. 2 (1976) 191-195
I. Javaid, M. T. Rahim, K. Ali, Families of regular graphs with constant metric dimension, Util. Math. 75 (2008) 21-34
S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217-229
R. A. Melter, I. Tomescu, Metric bases in digital geometry, Comput. Gr. Image Process. 25 (1984) 113-121
A. Sebo, 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, M. Imran, Metric dimension and R-sets of a connected graph, Graphs Comb. 27 (2011) 585-591
I. Tomescu, I. Javaid, On the metric dimension of the Jahangir graph, Bull. Math. Soc. Sci. Math. Roumanie 50(98) (2007) 371-376.