Domination and location in twin-free digraphs
Florent Foucaud, Shahrzad Heydarshahi, Aline Parreau · Discrete Applied Mathematics · 2020
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 γL(G) of a digraph G is the smallest size of a locating-dominating set of G. We investigate upper bounds on γ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 γ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, γL(G)≤4n5+1 holds, and there exist twin-free digraphs G with γL(G)=2(n−2)3. Improved bounds are proved for certain special cases. In particular, if G is twin-free and a tournament, or twin-free and acyclic, we prove γL(G)≤⌈n2⌉, which is tight in both cases.