On the metric dimension of generalized Petersen graphs

Abstract

Abstract A family G of connected graphs is said to be a family with constant metric dimension if its metric dimension is finite and does not depend upon the choice of G in G. In this paper, we study the metric dimension of the generalized Petersen graphs P(2m, m − 1) and give a partial answer to an open problem raised in [13]: Is the generalized Petersen graphs P(s, t), for s ≥ 7 and 3 ≤ t ≤ , a family of graphs with constant metric dimension? We prove that the generalized Petersen graphs P(2m, m − 1) have metric dimension equal to 3 for all odd m ≥ 3, and equal to 4 for all even m ≥ 4.