Tuomo Lehtilä

Locating-dominating sets: from graphs to oriented graphs

A locating-dominating set in an undirected graph is a subset of vertices $S$ such that $S$ is dominating and for every $u,v \notin S$, we have $N(u)\cap S\ne N(v)\cap S$. In this paper, we consider the oriented version of the problem. A locating-dominating set in an oriented graph is a set $S$ such that for every $w\in V$, $N[w]^-\cap S=\emptyset$ and for each pair of vertices $u,v\in V\setminus S$, $N^-(u)\cap S\ne N^-(v)\cap S$. We consider the following two parameters. Given an undirected graph $G$, we look for $\overset{\rightarrow}γ_{LD}(G)$ ($\overset{\rightarrow}Γ_{LD}(G))$ which is the size of the smallest (largest) optimal locating-dominating set over all orientations of $G$. In particular, if $D$ is an orientation of $G$, then $\overset{\rightarrow}γ_{LD}(G)\leqγ_{LD}(D)\leq\overset{\rightarrow}Γ_{LD}(G)$. For the best orientation, we prove that, for every twin-free graph $G$ on $n$ vertices, $\overset{\rightarrow}γ_{LD}(G)\le n/2$ proving a ``directed version'' of a conjecture on $γ_{LD}(G)$. Moreover, we give some bounds for $\overset{\rightarrow}γ_{LD}(G)$ on many graph classes and drastically improve the value $n/2$ for (almost) $d$-regular graphs by showing that $\overset{\rightarrow}γ_{LD}(G)\in O(\log d/d\cdot n)$ using a probabilistic argument. While $\overset{\rightarrow}γ_{LD}(G)\leqγ_{LD}(G)$ holds for every graph $G$, we give some graph classes graphs for which $\overset{\rightarrow}Γ_{LD}(G)\geqγ_{LD}(G)$ and some for which $\overset{\rightarrow}Γ_{LD}(G)\leq γ_{LD}(G)$. We also give general bounds for $\overset{\rightarrow}Γ_{LD}(G)$. Finally, we show that for many graph classes $\overset{\rightarrow}Γ_{LD}(G)$ is polynomial on $n$ but we leave open the question whether there exist graphs with $\overset{\rightarrow}Γ_{LD}(G)\in O(\log n)$.