The directed metric dimension of directed co-graphs

Abstract

A vertex $w$ resolves two vertices $u$ and $v$ in a directed graph $G$ if the distance from $w$ to $u$ is different to the distance from $w$ to $v$. A set of vertices $R$ is a resolving set for a directed graph $G$ if for every pair of vertices $u,v$ which are not in $R$ there is at least one vertex in $R$ that resolves $u$ and $v$ in $G$. The directed metric dimension of a directed graph $G$ is the size of a minimum resolving set for $G$. The decision problem Directed Metric Dimension for a given directed graph $G$ and a given number $k$ is the question whether $G$ has a resolving set of size at most $k$. In this paper, we study directed co-graphs. We introduce a linear time algorithm for computing a minimum resolving set for directed co-graphs and show that Directed Metric Dimension already is NP-complete for directed acyclic graphs.