Authors:
O. Hudry, A. Lobstein
Title:
The compared costs of domination, location-domination and identification
Source:
Discussiones Mathematicae Graph Theory
Received 21.07.2017, Revised 15.02.2018, Accepted 15.02.2018, doi: 10.7151/dmgt.2129

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 set C⊆ V is an r-dominating code if for all v∈V, we have Br(v)∩ C≠ \emptyset; it is an r-locating-dominating code if for all v∈V, we have Br(v)∩ C≠ \emptyset, and for any two distinct non-codewords x∈V\setminus C, y∈V\setminus 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≠ \emptyset, 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

Links:
PDF