On the metric dimension of a graph (Q1265351)

The metric dimension of a graph is the minimal order of a subset such that for any pair of vertices of the graph it contains a vertex which is at a different distance to them both. It is shown that in a graph of metric dimension \(k\), any subgraph of order \(2^k+1\) must have more than \(2^{k-1}-1\) missing edges to be complete.