Computing the metric dimension of wheel related graphs
Abstract An ordered set W = { w 1 , … , w k } ⊆ V ( G ) of vertices of G is called a resolving set or locating set for G if every vertex is uniquely determined by its vector of distances to the vertices in W . A resolving set of minimum cardinality is called a basis for G and this cardinality is the metric dimension or location number of G, denoted by β ( G ) . In this paper, we study the metric dimension of certain wheel related graphs, namely m -level wheels, an infinite class of convex polytopes and antiweb-gear graphs denoted by W n , m , Q n and AWJ 2 n , respectively. We prove that these infinite classes of wheel related graphs have unbounded metric dimension. The study of an infinite class of convex polytopes generated by wheel, denoted by Q n also gives a negative answer to an open problem proposed by Imran et al. (2012) in [8]: Open Problem : Is it the case that the graph of every convex polytope has constant metric dimension? It is natural to ask for characterization of graphs with unbounded metric dimension.