The compared costs of domination, location-domination and identification
| Autor: | Olivier Hudry, Antoine Lobstein |
|---|---|
| Přispěvatelé: | Télécom ParisTech, Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2020 |
| Předmět: |
05c90
graph theory twin-free graph 2010 Mathematics Subject Classification: 68R10 dominating set 94c12 0102 computer and information sciences 02 engineering and technology [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] locating-dominating code 01 natural sciences Combinatorics identifying code 94b60 [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] 94b65 QA1-939 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics Mathematics 68r10 Applied Mathematics twin-free graph 020206 networking & telecommunications Finite graph 010201 computation theory & mathematics |
| Zdroj: | Discussiones Mathematicae Graph Theory, Vol 40, Iss 1, Pp 127-147 (2020) Discussiones Mathematicae Graph Theory Discussiones Mathematicae Graph Theory, University of Zielona Góra, 2020, 40 (1), pp.127-147. ⟨10.7151/dmgt.2129⟩ |
| ISSN: | 2083-5892 1234-3099 |
| DOI: | 10.7151/dmgt.2129 |
| Popis: | International audience; 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 = ∅; it is an r-locating-dominating code if for all v ∈ V , we have B r (v) ∩ C = ∅, and for any two distinct non-codewords x ∈ V \ C, y ∈ V \ 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 = ∅, 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|