- Tytuł:
- The Compared Costs of Domination Location-Domination and Identification
- Autorzy:
-
Hudry, Olivier
Lobstein, Antoine - Powiązania:
- https://bibliotekanauki.pl/articles/32083840.pdf
- Data publikacji:
- 2020-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
graph theory
dominating set
locating-dominating code
identifying code
twin-free graph - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 127-147
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł