A note on locating sets in twin-free graphs

Nicolas Bousquet, Quentin Chuet, Victor Falgas-Ravry, Amaury Jacques, Laure Morelle

Published 2024-05-28Version 1

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\"owenstein and Sasse from 2016, and makes some progress towards the well-studied locating-dominating conjecture of Garijo, Gonz\'alez and M\'arquez.