A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

Locating-dominating sets: From graphs to oriented graphs




TekijätBousquet Nicolas, Deschamps Quentin, Lehtilä Tuomo, Parreau Aline

KustantajaELSEVIER

Julkaisuvuosi2023

JournalDiscrete Mathematics

Tietokannassa oleva lehden nimiDISCRETE MATHEMATICS

Lehden akronyymiDISCRETE MATH

Artikkelin numero 113124

Vuosikerta346

Numero1

Sivujen määrä19

ISSN0012-365X

eISSN1872-681X

DOIhttps://doi.org/10.1016/j.disc.2022.113124

Verkko-osoitehttps://doi.org/10.1016/j.disc.2022.113124

Rinnakkaistallenteen osoitehttps://research.utu.fi/converis/portal/detail/Publication/176566249


Tiivistelmä

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; S). 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/).


Ladattava julkaisu

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





Last updated on 2024-26-11 at 18:37