The Compared Costs of Domination, Location-Domination and Identification - Equipe Cybersécurité et Cryptographie Accéder directement au contenu
Article Dans Une Revue Discussiones Mathematicae Graph Theory Année : 2020

The Compared Costs of Domination, Location-Domination and Identification

Olivier Hudry
Antoine Lobstein

Résumé

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.
Fichier principal
Vignette du fichier
DMGT-2129.pdf (238.73 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01702966 , version 1 (30-11-2020)

Identifiants

Citer

Olivier Hudry, Antoine Lobstein. The Compared Costs of Domination, Location-Domination and Identification. Discussiones Mathematicae Graph Theory, 2020, 40 (1), pp.127-147. ⟨10.7151/dmgt.2129⟩. ⟨hal-01702966⟩
213 Consultations
42 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More