On the metric dimension of rotationally-symmetric convex polytopes
Keywords:
Metric dimension, Basis, Resolving set, Prism, Antiprism, Convex polytopesAbstract
Metric dimension is a~generalization of affine dimension to arbitrary metric spaces (provided a resolving set exists). Let $\mathcal{F}$ be a family of connected graphs $G_{n}$ : $\mathcal{F} = (G_{n})_{n}\geq 1$ depending on $n$ as follows: the order $|V(G)| = \varphi(n)$ and $\lim\limits_{n\rightarrow \infty}\varphi(n)=\infty$. If there exists a constant $C > 0$ such that $dim(G_{n}) \leq C$ for every $n \geq 1$ then we shall say that $\mathcal{F}$ has bounded metric dimension, otherwise $\mathcal{F}$ has unbounded metric dimension. If all graphs in $\mathcal{F}$ have the same metric dimension, then $\mathcal{F}$ is called a family of graphs with constant metric dimension.\\ In this paper, we study the metric dimension of some classes of convex polytopes which are rotationally-symmetric. It is shown that these classes of convex polytoes have the constant metric dimension and only three vertices chosen appropriately suffice to resolve all the vertices of these classes of convex polytopes. It is natural to ask for the characterization of classes of convex polytopes with constant metric dimension.
Downloads
References
M. Bača, Labelings of two classes of convex polytopes, Utilitas Math. 34 (1988) 24-31.
M. Bača, On magic labellings of convex polytopes, Ann. Discrete Math. 51 (1992) 13-16.
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 cartesian products of graphs, SIAM J. Discrete Math. 21(2) (2007) 423-441.
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.
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, New York (1979).
F. Harary and R. A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191-195.
C. Hernando, M. Mora, I. M. Pelayo, C. Seara, J. Cáceres, and M. L. Puertas, On the metric dimension of some families of graphs, Electron. Notes Discrete Math. 22 (2005) 129-133.
M. Imran, A. Q. Baig, and A. Ahmad, Families of plane graphs with constant metric dimension, Utilitas Math. 88 (2012) 43-57.
M. Imran, A. Q. Baig, M. K. Shafiq, and A. Semaničová-Feňovčíková, Classes of convex polytopes with constant metric dimension, Utilitas Math. 90 (2013) 85-99.
I. Javaid, M. T. Rahim, and K. Ali, Families of regular graphs with constant metric dimension, Utilitas Math. 75 (2008) 21-33.
M. A. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Stat. 3(2) (1993) 203-236.
E. Jucovič, Konvexné Mnohosteny, Veda, Bratislava (1981).
S. Khuller, B. Raghavachari, and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70(3) (1996) 217-229.
S. Khuller, B. Raghavachari, and A. Rosenfeld, Localization in graphs, Technical Report CS-TR-3326, University of Maryland (1994).
R. A. Melter and I. Tomescu, Metric bases in digital geometry, Comput. Vision Graphics Image Process. 25(1) (1984) 113-121.
J. Peters-Fransen and O. R. Oellermann, The metric dimension of Cartesian products of graphs, Utilitas Math. 69 (2006) 33-41.
P. J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549-559.
P. J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22(4) (1988) 445-455.
I. Tomescu and M. Imran, On metric and partition dimensions of some infinite regular graphs, Bull. Math. Soc. Sci. Math. Roumanie 52(100)(4) (2009) 461-472.
I. Tomescu and I. Javaid, On the metric dimension of the Jahangir graph, Bull. Math. Soc. Sci. Math. Roumanie 50(98)(4) (2007) 371-376.
