Domination and location in twin-free digraphs

Abstract

A dominating set $D$ in a digraph is a set of vertices such that every vertex is either in $D$ or has an in-neighbour in $D$. A dominating set $D$ of a digraph is locating-dominating if every vertex not in $D$ has a unique set of in-neighbours within $D$. The location-domination number ${\gamma }_L(G)$ of a digraph $G$ is the smallest size of a locating-dominating set of $G$. We investigate upper bounds on ${\gamma }_L(G)$ in terms of the order of $G$. We characterize those digraphs with location-domination number equal to the order or the order minus one. Such digraphs always have many twins: vertices with the same (open or closed) in-neighbourhoods. Thus, we investigate the value of ${\gamma }_L(G)$ in the absence of twins and give a general method for constructing small locating-dominating sets by the means of special dominating sets. In this way, we show that for every twin-free digraph $G$ of order $n$, ${\gamma }_L(G)\le \frac{4n}{5}$ holds, and there exist twin-free digraphs $G$ with ${\gamma }_L(G)=\frac{2(n-2)}{3}$. If moreover $G$ is a tournament or is acyclic, the bound is improved to ${\gamma }_L(G)\le \lceil \frac{n}{2}\rceil$, which is tight in both cases.