The effect of vertex or edge deletion on the metric dimension of graphs
Linda Eroh, Paul Feit, Cong X. Kang, Eunjeong Yi · Journal of Combinatorics · 2015
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(Gv)dim(G) = k.For an arbitrary edge e of any graph G, we prove that dim(Ge) ≤ dim(G) + 2. We also prove that dim(Ge) ≥ dim(G) -1 for G belonging to a rather general class of graphs.Moreover, we give an example showing that dim(G)dim(Ge) can be arbitrarily large.