Locating-dominating sets in local tournaments (Q6162022)

In the present paper, the authors consider locating-dominating sets in digraphs. To state some of the main results, several definitions from the paper are first needed. A finite and loopless digraph \(D\) is simple if there is at most one arc between any two distinct vertices. Let \(D\) be any digraph and let \(x\), \(y\) be two distinct vertices of \(D\). We say that vertex \(x\) dominates vertex \(y\) if there is an arc from \(x\) to \(y\). In such a case, \(y\) is an out-neighbour of \(x\) and \(x\) is an in-neighbour of \(y\). Let \(v\) be a vertex of \(D\). The set of all in-neighbours of \(v\), denoted as \(N^- (v)\), is called the open in-neighbourhood of \(v\), and the set of all out-neighbours of \(v\), denoted as \(N^+(v)\), is called the open out-neighbourhood of \(v\). In addition, the closed in-neighbourhood of \(v\) is the set \(N^-[v]=N^-(v) \cup \{ v \}\) and the closed out-neighbourhood of \(v\) is the set \(N^+[v]=N^+(v) \cup \{ v \}\). Two distinct vertices \(x\) and \(y\) of \(D\) are called twins if \(N^-(x)=N^-(y)\) or \(N^-[x]=N^-[y]\). Moreover, \(x\) and \(y\) are quasi twins if \(N^-(x)=N^-[y]\) or \(N^-(y)=N^-[x]\). Then, \(D\) is called twin-free if it contains no twins, and \(D\) is called quasi-twin-free if it contains no twins or quasi-twins. Furthermore, we say that a digraph \(D\) is connected if for every vertices \(x\) and \(y\) of \(D\) there exists a (not necessarily directed) path from \(x\) to \(y\). On the other hand, \(D\) is strongly connected if for every vertices \(x\) and \(y\) of \(D\) there is a directed path from \(x\) to \(y\) and a directed path from \(y\) to \(x\). In addition, a vertex \(s\) of \(D\) is a supervising vertex if for any vertex \(v\) of \(D\) there exists a directed path from \(s\) to \(v\). A digraph \(D\) is a tournament if there is exactly one arc between every pair of distinct vertices of \(D\). On the other hand, a digraph \(D\) is called a local tournament if it is simple and the in-neighbourhood and the out-neighbourhood of every vertex of \(D\) induce tournaments. Similarly, a digraph is semicomplete if there is at least one arc between every pair of vertices and \(D\) is locally in-semicomplete if the in-neighbourhood of every vertex of \(D\) induces a semicomplete digraph. Let \(D\) be a digraph. We say that a set of vertices \(S\) of \(D\) is a dominating set of \(D\) if any vertex not in \(S\) is dominated by some vertex in \(S\). The smallest cardinality of a dominating set of \(D\), denoted as \(\gamma (D)\), is called the domination number of \(D\). On the other hand, a locating set \(S\) of \(D\) is a subset of vertices of \(D\) such that for any two distinct vertices \(x,y \in V(D) \setminus S\), there exists a vertex from \(S\) that dominates exactly one vertex among \(x\) and \(y\). The smallest cardinality of a locating set of \(D\) is denoted as \(\gamma^L (D)\). Finally, a set of vertices of \(D\) that is locating and dominating is called a locating-dominating set, and the minimum cardinality of a locating-dominating set of \(D\), denoted by \(\gamma^{LD} (D)\), is the location-domination number of \(D\). In Sections 3 and 4 of the paper, the authors prove the following main result. Theorem. A connected local tournament \(D\) of order \(n\) satisfies \(\gamma^{LD} (D) \leq \left \lceil \frac{n}{2} \right \rceil\). Moreover, among other things, the following results are stated in Section 5 of the paper. Theorem. Let \(D\) be a twin-free digraph on \(n\) vertices containing a supervising vertex, then \(\gamma^{LD}(D) \leq \frac{3n}{4}\). Moreover, if \(D\) is quasi-twin-free, then \(\gamma^{LD}(D) \leq \frac{2n}{3}\). Corollary. Let \(D\) be a twin-free strongly connected digraph on \(n\) vertices, then \(\gamma^{LD}(D) \leq \frac{3n}{4}\). Moreover, if \(D\) is quasi-twin-free, then \(\gamma^{LD}(D) \leq \frac{2n}{3}\). Corollary. Let \(D\) be a twin-free locally in-semicomplete digraph on \(n\) vertices, then \(\gamma^{LD}(D) \leq \frac{3n}{4}\). Moreover, if \(D\) is quasi-twin-free, then \(\gamma^{LD}(D) \leq \frac{2n}{3}\).