Menu
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].