2011/12/11 by Behrooz Bagheri Gh., Gh., Behrooz Bagheri, Mohsen Jannesari +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #math.CO
paper · pdf · doi:10.48550/arxiv.1112.2326
6 pages
arxiv created 2011/12/11 · openalex publication_date 2011/12/11 · arxiv updated 2011/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A set W⊆ V(G) is called a resolving set, 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, we prove that in a connected graph G of order n, β(G)≤ n-γ(G), where γ(G) is the domination number of G, and the equality holds if and only if G is a complete graph or a complete bipartite graph Ks,t, s,t≥ 2. Then, we obtain new bounds for β(G) in terms of minimum and maximum degree of G.