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.