The metric dimension and girth of graphs

Abstract

A set W ⊆ V (G) is called a resolving set for G, if for each two distinct vertices u, v ∈ V (G) there exists w 2 W such that d(u,w) ≠ d(v,w), where d(x, y) is the distance between the vertices x and y. The minimum cardinality of a resolving set for G is called the metric dimension of G, and denoted by dim(G). In this paper, it is proved that in a connected graph G of order n which has a cycle, dim(G) ≤ n-g(G)+2, where g(G) is the length of the shortest cycle in G, and the equality holds if and only if G is a cycle, a complete graph or a complete bipartite graph Ks,t, s, t ≥ 2. © 2015 Iranian Mathematical Society.