Back to Search
Start Over
Locating-dominating sets in local tournaments.
- Source :
-
Discrete Applied Mathematics . Oct2023, Vol. 337, p14-24. 11p. - Publication Year :
- 2023
-
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 ∈ 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 γ L D (D). Foucaud, Heydarshahi and Parreau proved that any twin-free digraph D satisfies γ L D (D) ≤ 4 n 5 + 1 but conjectured that this bound can be lowered to 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 exactly one arc between every pair of vertices, then γ L D (D) ≤ ⌈ n 2 ⌉. 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 γ L D (D) ≤ 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *DOMINATING set
*DIRECTED graphs
*TOURNAMENTS
*LOGICAL prediction
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 337
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 164280757
- Full Text :
- https://doi.org/10.1016/j.dam.2023.04.010