An infinite Class of Convex Polytopes with Constant Metric Dimension

Abstract

A family $\mathcal{G}$ of connected graphs is a family with constant metric dimension if $\dim (G)$ is finite and does not depend upon the choice of $G$ in $\mathcal{G}$. The metric dimension of some classes of plane graphs has been determined in references [3], [4], [5], [12], [14], and [18], while the metric dimension of some families of convex polytopes has been studied in references [8], [9], [10], and [11]. The following open problem was raised in reference [11].

Open Problem [11]: Let $G$ be the graph of a convex polytope which is obtained by joining the graph of two different convex polytopes $G_1$ and $G_2$ (such that the outer cycle of $G_1$ is the inner cycle of $G_2$) both having constant metric dimension. Is it the case that $G$ will always have constant metric dimension?

In this paper, we extend this study to an infinite class of convex polytopes obtained as a combination of the graph of an antiprism $A_n$ [1] and the graph of convex polytope $Q_n$ [2], such that the outer cycle of $A_n$ is the inner cycle of $Q_n$. It is natural to ask for the characterization of classes of convex polytopes with constant metric dimension. Note that the problem of determining whether $\dim (G)<k$ is an NP-complete problem [7].