2012/03/07 by Mohsen Jannesari, Jannesari, Mohsen
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1203.1584
6 pages
arxiv created 2012/03/10 · arxiv updated 2012/03/13
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∈ 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 β(G). In this paper, it is proved that in a connected graph G of order n which has a cycle, β(G)≤ n-g(G)+2, where g(G) is the length of a 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.