A note on locating-dominating sets in twin-free graphs
In this short note, we prove that every twin-free graph on n vertices contains a locating-dominating set of size at most ⌈ 5 8 n ⌉ . This improves the earlier bound of ⌊ 2 3 n ⌋ 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.
Authors
- Nicolás Bousquet (ORCID: https://orcid.org/0000-0003-0170-0503)
- Victor Falgas‐Ravry (ORCID: https://orcid.org/0000-0001-8631-4745)
- Laure Morelle (ORCID: https://orcid.org/0009-0000-1001-1801)
- Quentin Chuet
- Amaury Jacques
Publication Details
- Journal
- Discrete Mathematics
- Published
- 2024-10-31
- DOI
- https://doi.org/10.1016/j.disc.2024.114297
- Citations
- 1
- Primary Topic
- Graph Labeling and Dimension Problems
- Type
- article
- Field-Weighted Citation Impact
- 0.36
Funders
- Agence Nationale de la Recherche
- Vetenskapsrådet