Locating-dominating sets: From graphs to oriented graphs

Abstract

<p>A locating-dominating set of an undirected graph is a subset of vertices S such that S is dominating and for every u, v is not an element of S, the neighbourhood of u and v on S are distinct (i.e. N(u) & cap; S &NOTEQUexpressionL; N(v) & cap; <i>S</i>). Locating-dominating sets have received a considerable attention in the last decades. 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 each w is an element of V \ S, N-(w) & cap; S &NOTEQUexpressionL; Phi and for each pair of distinct vertices u, v is an element of V \ S, N-(u) & cap; S &NOTEQUexpressionL; N-(v) & cap; S. We consider the following two parameters. Given an undirected graph G, we look for (gamma)over the arrow(LD) (G) ((gamma)over the arrow(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 (gamma)over the arrow(LD)(G) <= gamma(LD)(D) <= (gamma)over the arrow(LD)(G) where gamma(LD)(D) is the minimum size of a locating-dominating set of D. For the best orientation, we prove that, for every twin-free graph G on n vertices, (gamma)over the arrow(LD)(G) <= n/2 which proves a "directed version " of a widely studied conjecture on the location-domination number. As a side result we obtain a new improved upper bound for the location-domination number in undirected trees. Moreover, we give some bounds for (gamma)over the arrow(LD)(G) on many graph classes and drastically improve the value n/2 for (almost) d-regular graphs by showing that (gamma)over the arrow(LD)(G) is an element of O (log d/d center dot n) using a probabilistic argument. While (gamma)over the arrow(LD)(G) <= gamma(LD)(G) holds for every graph G, we give some graph classes such as outerplanar graphs for which (gamma)over the arrow(LD)(G) >= gamma(LD)(G) and some for which (gamma)over the arrow(LD)(G) <= gamma(LD)(G) such as complete graphs. We also give general bounds for (gamma)over the arrow(LD)(G ) such as (gamma)over the arrow(LD)(G) >= alpha(G). Finally, we show that for many graph classes (gamma)over the arrow(LD)(G) is polynomial on n but we leave open the question whether there exist graphs with (gamma)over the arrow(LD)(G) is an element of O (log n). (c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).<br></p>