Journal of Combinatorics
Volume 6 (2015)
The effect of vertex or edge deletion on the metric dimension of graphs
Pages: 433 – 444
The metric dimension $\dim(G)$ of a graph $G$ is the minimum cardinality of a set of vertices such that every vertex of $G$ is uniquely determined by its vector of distances to the chosen vertices. Let $v$ and $e$ respectively denote a vertex and an edge of a graph $G$. We show that, for any integer $k$, there exists a graph $G$ such that $\dim(G-v) - \dim(G) = k$. For an arbitrary edge $e$ of any graph $G$, we prove that $\dim(G-e) \leq \dim(G) + 2$. We also prove that $\dim(G-e) \geq \dim(G) - 1$ for $G$ belonging to a rather general class of graphs. Moreover, we give an example showing that $\dim(G) - \dim(G-e)$ can be arbitrarily large.
distance, resolving set, metric dimension, vertex deletion, edge deletion
2010 Mathematics Subject Classification