Journal of Combinatorics

Volume 6 (2015)

Number 4

The effect of vertex or edge deletion on the metric dimension of graphs

Pages: 433 – 444



Linda Eroh (University of Wisconsin, Oshkosh, Wisconsin, U.S.A.)

Paul Feit (University of Texas of the Permian Basin, Odessa, Tx., U.S.A.)

Cong X. Kang (Texas A&M University, Galveston, Tx., U.S.A.)

Eunjeong Yi (Texas A&M University, Galveston, Tx., U.S.A.)


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


Published 31 July 2015