Locating-dominating sets in local tournaments

Abstract: A dominating set in a directed graph is a set of vertices

S

such that all the vertices that do not belong to

S

have an in-neighbour in

S

. A locating set

S

is a set of vertices such that all the vertices that do not belong to

S

are characterized uniquely by the in-neighbours they have in

S

, i.e. for every two vertices

u

and

v

that are not in

S

, there exists a vertex

s i n S

that dominates exactly one of them. The size of a smallest set of a directed graph

D

which is both locating and dominating is denoted by

g a m m a^{L D} (D)

. Foucaud, Heydarshahi and Parreau proved that any twin-free digraph

D

satisfies

g a m m a^{L D} (D) l e q f r a c 4 n 5 + 1

but conjectured that this bound can be lowered to

f r a c 2 n 3

. The conjecture is still open. They also proved that if

D

is a tournament, i.e. a directed graph where there is one arc between every pair of vertices, then

g a m m a^{L D} (D) l e q l c e i l f r a c n 2 c e i l

. The main result of this paper is the generalization of this bound to connected local tournaments, i.e. connected digraphs where the in- and out-neighbourhoods of every vertex induce a tournament. We also prove

g a m m a^{L D} (D) l e q f r a c 2 n 3

for all quasi-twin-free digraphs

D

that admit a supervising vertex (a vertex from which any vertex is reachable). This class of digraphs generalizes twin-free acyclic graphs, the most general class for which this bound was known.

Review text

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}\).

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Locating-dominating sets in local tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6162022)