The Simultaneous Metric Dimension of Graph Families

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.

Back to all abstracts