  A set $R \subseteq V(G)$ is a resolving set of a graph $G$ if for all
distinct vertices $v,u \in V(G)$ there exists an element $r \in R$ such that
$d(r,v) \neq d(r,u)$. The metric dimension $\dim(G)$ of the graph $G$ is the
minimum cardinality of a resolving set of $G$. A resolving set with cardinality
$\dim(G)$ is called a metric basis of $G$. We consider vertices that are in all
metric bases, and we call them basis forced vertices. We give several
structural properties of sparse and dense graphs where basis forced vertices
are present. In particular, we give bounds for the maximum number of edges in a
graph containing basis forced vertices. Our bound is optimal whenever the
number of basis forced vertices is even. Moreover, we provide a method of
constructing fairly sparse graphs with basis forced vertices. We also study
vertices which are in no metric basis in connection to cut-vertices and
pendants. Furthermore, we show that deciding whether a vertex is in all metric
bases is co-NP-hard, and deciding whether a vertex is in no metric basis is
NP-hard.

Combinatorics