HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

The Compared Costs of Domination, Location-Domination and Identification

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 = ∅; 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.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-01702966
Contributor : Antoine Lobstein Connect in order to contact the contributor
Submitted on : Monday, November 30, 2020 - 12:30:53 PM
Last modification on : Monday, January 24, 2022 - 11:43:20 AM
Long-term archiving on: : Monday, March 1, 2021 - 6:54:56 PM

File

DMGT-2129.pdf
Files produced by the author(s)

Identifiers

Citation

Olivier Hudry, Antoine Lobstein. The Compared Costs of Domination, Location-Domination and Identification. Discussiones Mathematicae Graph Theory, University of Zielona Góra, 2020, 40 (1), pp.127-147. ⟨10.7151/dmgt.2129⟩. ⟨hal-01702966⟩

Share

Metrics

Record views

158

Files downloads

26