Logo image
Se connecter
A note on locating-dominating sets in twin-free graphs
Article de revue   Open Access   Avec comité de lecture

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

Nicolas Bousquet, Quentin Chuet, Victor Falgas-Ravry, Amaury Jacques et Laure Morelle
Discrete Mathematics, Vol.348(2)
02/2025

Résumé

Locating sets Locating-dominating sets Graph partitions 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 $[\frac{5}{8}n]$. This improves the earlier bound of $[\frac{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.

Fichiers et liens (2)

url
Find in HALAfficher
url
https://doi.org/10.1016/j.disc.2024.114297Afficher
Published (Version of record) Ouvrir

Indicateurs

1 Consultations de la notice

Détails

Logo image