The Compared Costs of Domination, Location-Domination and Identification
Discussiones Mathematicae Graph Theory, Vol. 40(1), pp. 127-147, 2020.
http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.2129
Olivier HUDRY (#) & Antoine LOBSTEIN (*)
(#) Département Informatique et Réseaux, LTCI,
Télécom ParisTech, Université Paris-Saclay,
46 rue Barrault, 75634 Paris Cedex 13 - France
olivier.hudry@telecom-paristech.fr
(*) Centre National de la Recherche Scientifique,
Laboratoire de Recherche en Informatique, UMR 8623,
Université Paris-Sud, Université Paris-Saclay,
Bâtiment 650 Ada Lovelace, 91405 Orsay Cedex - France
antoine.lobstein@lri.fr
Abstract. Let G=(V,E) be a finite graph and r ≥ 1 be an integer. For v ∈ V, let Br(v)={x ∈ V: d(v,x) ≤ r} be the ball of radius r centered at v. A subset C of V is an r-dominating code if for all v ∈ V, we have Br(v) ∩ C ≠ ∅; it is an r-locating-dominating code if for all v ∈ V, we have Br(v) ∩ C ≠ ∅ and for any two distinct non-codewords x ∈ V\C, y ∈ V\C, we have Br(x) ∩ C ≠ Br(y) ∩ C; it is an r-identifying code if for all v ∈ V, we have Br(v) ∩ C ≠ ∅ and for any two distinct vertices x ∈ V, y ∈ V, we have Br(x) ∩ C ≠ Br(y) ∩ C. We denote by γr(G) (respectively, ldr(G) and idr(G)) the smallest possible cardinality of an r-dominating code (respectively, an r-locating-dominating code and an r-identifying code). We study how small and how large the three differences idr(G)-ldr(G), idr(G)-γr(G) and ldr(G)-γr(G) can be.