Geodesic
The Compared Costs of Domination Location-Domination and Identification
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 127-147

Voir la notice de l'article provenant de la source Library of Science

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 set C ⊆ 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.
Keywords: graph theory, dominating set, locating-dominating code, identifying code, twin-free graph 
@article{DMGT_2020_40_1_a8,
     author = {Hudry, Olivier and Lobstein, Antoine},
     title = {The {Compared} {Costs} of {Domination} {Location-Domination} and {Identification}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {127--147},
     publisher = {mathdoc},
     volume = {40},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a8/}
}
TY  - JOUR
AU  - Hudry, Olivier
AU  - Lobstein, Antoine
TI  - The Compared Costs of Domination Location-Domination and Identification
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 127
EP  - 147
VL  - 40
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a8/
LA  - en
ID  - DMGT_2020_40_1_a8
ER  - 
%0 Journal Article
%A Hudry, Olivier
%A Lobstein, Antoine
%T The Compared Costs of Domination Location-Domination and Identification
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 127-147
%V 40
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a8/
%G en
%F DMGT_2020_40_1_a8
Hudry, Olivier; Lobstein, Antoine. The Compared Costs of Domination Location-Domination and Identification. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 127-147. http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a8/