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 B_{r}(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 B_{r}(v)∩ C≠ \emptyset; it is an r-locating-dominating code if for all v∈V, we have B_{r}(v)∩ C≠ \emptyset, and for any two distinct non-codewords x∈V\setminus C, y∈V\setminus C, we have B_{r}(x)∩ C ≠ B_{r}(y)∩ C; it is an r-identifying code if for all v∈V, we have B_{r}(v)∩ C≠ \emptyset, and for any two distinct vertices x∈V, y∈V, we have B_{r}(x)∩ C ≠ B_{r}(y)∩ C. We denote by γ_{r}(G) (respectively, ld_{r}(G) and id_{r}(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 id_{r}(G)-ld_{r}(G), id_{r}(G)-γ_{r}(G) and ld_{r}(G)-γ_{r}(G) can be. | |
Keywords: graph theory, dominating set, locating-dominating code, identifying code, twin-free graph | |
Links: |