Resolvability in graphs and the metric dimension of a graph
type: Item
instance of: scholarly article
title: Resolvability in graphs and the metric dimension of a graph
zbMATH Open document ID: 0958.05042
DOI: 10.1016/S0166-218X(00)00198-0
author: Gary Chartrand
author: Linda Eroh
author: Mark A. Johnson
author: Ortrud R. Oellermann
published in: Discrete Applied Mathematics
publication date: 2001-02-27T00:00:00Z
review text: For an ordered set \(W=\{w_{1},\ldots ,w_{k}\}\) of vertices in a connected graph \(G\) and a vertex \(v\) of \(G\), the metric representation of \(v\) with respect to \(W\) is the \(k\)-vector \(r(v|W)=(d(v,w_{1}),\ldots ,d(v,w_{k}))\). The set \(W\) is said to be a resolving set for \(G\) if \(r(u|W)=r(v|W)\) implies that \(u=v\) for all pairs \(u\), \(v\) of vertices of \(G\). The metric dimension \(\dim(G)\) of \(G\) is the minimum cardinality of a resolving set for \(G\). In this paper bounds on \(\dim(G)\) are presented in terms of the order and the diameter of \(G\). All connected graphs of order \(n\) having dimension 1, \(n-2\), or \(n-1\) are determined and a new proof for the dimension of a tree is also presented. From this result sharp bounds on the metric dimension of unicyclic graphs are established. It is shown that \(\dim(H)\leq \dim(H\times K_{2})\leq \dim(H)+1\) for every connected graph \(H\). Moreover, it is shown that for every positive real number \(\varepsilon \), there exists a connected graph \(G\) and a connected induced subgraph \(H\) of \(G\) such that \(\dim(G)/\dim(H)<\varepsilon\).
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1512448
zbMATH Keywords: distance
zbMATH Keywords: diameter
zbMATH Keywords: metric dimension
zbMATH Keywords: tree
zbMATH Keywords: Cartesian product
zbMATH Keywords: unicyclic graph
zbMATH Keywords: basis
Wikidata QID: Q56551548
MaRDI profile type: Publication
cites work: Q4198056
cites work: Q4119237
cites work: Q4532377
cites work: Q4075485
cites work: Q3803159
DBLP publication ID: journals/dam/ChartrandEJO00
description: scientific article; zbMATH DE number 1512448