A note on locating-dominating sets in twin-free graphs

Abstract

In this short note, we prove that every twin-free graph on $n$ vertices contains a locating-dominating set of size at most $\lceil \frac{5}{8}n\rceil$. This improves the earlier bound of $\lfloor \frac{2}{3}n\rfloor$ due to Foucaud, Henning, Löwenstein and Sasse from 2016, and makes some progress towards the well-studied locating-dominating conjecture of Garijo, González and Márquez.

5 pages, 1 figure. Changed title. To appear in Discrete Mathematics 348(2), 2025