Characterization of \(n\)-vertex graphs with metric dimension \({n-3}\). (Q2925938)

Let \(G\) be a connected graph and \(W=\{ w_1,w_2, \dots w_k \}\) an ordered set of vertices of \(G\). The ordered \(k\)-vector \(r(v| W):= \left( d(v,w_1), d(v,w_2), \dots, d(v,w_k)\right)\) is called the metric representation of the vertex \(v\) with respect to the set \(W\), where \(d(x,y)\) denotes the distance between vertices \(x\) and \(y\) in \(G\). A set \(W\) is called a resolving set for a graph \(G\) if distinct vertices of \(G\) have distinct metric representations with respect to \(W\). The minimum cardinality of a resolving set for \(G\) is called its metric dimension. In this paper, the authors completely characterize all graphs of order \(n\) with metric dimension \(n-3\). In the list of all possible graphs, they use a concept of the twin graphs and they show that all such twin graphs of graphs with metric dimension \(n-3\) have at most five vertices.