Contents Online

# Journal of Combinatorics

## Volume 6 (2015)

### Number 4

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

Pages: 433 – 444

DOI: http://dx.doi.org/10.4310/JOC.2015.v6.n4.a2

#### Authors

#### Abstract

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.

#### Keywords

distance, resolving set, metric dimension, vertex deletion, edge deletion

#### 2010 Mathematics Subject Classification

05C12

Published 31 July 2015