zbMATH — the first resource for mathematics

The theory and applications of resolvability in graphs (a survey). (English) Zbl 1039.05029
For an ordered set \(W=\{w_{1},\dots ,w_{k}\}\) of vertices and a vertex \(v\) in a connected graph \(G\), the metric representation of \(v\) with respect to \(W\) is the vector \(r(v| W)=(d(v,w_{1}),\dots ,d(v,w_{k}))\), where \(d(x,y)\) represents the distance between the vertices \(x\) and \(y\). The set \(W\) is said to be a resolving set for \(G\) if distinct vertices of \(G\) have distinct representations with respect to \(W\). The minimum cardinality of a resolving set for \(G\) is called its metric dimension dim(\(G\)). These concepts have been extended in various ways and studied for different subjects in graph theory, including such aspects as the partition of the vertex set, decomposition, orientation, domination, and coloring in graphs. Many invariants arising from the study of resolving sets in graph theory offer subjects for applicable research. In this paper results and open questions on resolvability in graphs are surveyed.

05C12 Distance in graphs
05C20 Directed graphs (digraphs), tournaments
05C90 Applications of graph theory