# The Simultaneous Metric Dimension of Graph Families

###
Ortrud Oellermann

University of Winnipeg

####
Yunior Ramirez-Cruz

Universitat Rovira i Virgili

####
Juan-Alberto Rodriguez-Velazquez

Universitat Rovira i Virgili

PDF

**Minisymposium:**
METRIC DIMENSION AND RELATED PARAMETERS

**Content:**
Let $x, y$ and $v$ be vertices of a graph $G$. Then $v$ is said to resolve the pair $x, y$ if $d_G(x,v) \ne d_G(y,v)$. A set $S$ of vertices of $G$ is a metric generator for $G$ if every pair of vertices of $G$ is resolved by some vertex of $S$. A smallest metric generator of $G$ is called a metric basis and its cardinality the metric dimension of $G$. Let $F=\{G_1,G_2, \ldots, G_n\}$ be a family of graphs on a common (labeled) vertex set $V$. A subset $S$ of $V$ is a simultaneous metric generator of $F$ if $S$ is a metric generator for every member of $F$. A smallest simultaneous metric generator for $F$ is called a simultaneous metric basis and its cardinality the simultaneous metric dimension of $F$. We show that the problem of finding the simultaneous metric dimension of families of graphs is NP-hard even for families of graphs (such as trees) for which the metric dimension of each member can be determined in polynomial time. We establish sharp upper and lower bounds for the simultaneous metric dimension of certain families of trees.