Minimum density of identifying codes of king grids

Rennan Dantas 1 Rudini Sampaio 2 Frédéric Havet 3
3 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : A set C ⊆ V (G) is an identifying code in a graph G if for all v ∈ V (G), C[v] = ∅, and for all distinct u, v ∈ V (G), C[u] = C[v], where C[v] = N [v] ∩ C and N [v] denotes the closed neighbourhood of v in G. The minimum density of an identifying code in G is denoted by d * (G). In this paper, we study the density of king grids which are strong product of two paths. We show that for every king grid G, d * (G) ≥ 2/9. In addition, we show this bound is attained only for king grids which are strong products of two infinite paths. Given k ≥ 3, we denote by K k the (infinite) king strip with k rows. We prove that d * (K 3) = 1/3, d * (K 4) = 5/16, d * (K 5) = 4/15 and d * (K 6) = 5/18. We also prove that 2 9 + 8 81k ≤ d * (K k) ≤ 2 9 + 4 9k for every k ≥ 7.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01634305
Contributor : Frederic Havet <>
Submitted on : Monday, November 13, 2017 - 10:41:00 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Document(s) archivé(s) le : Wednesday, February 14, 2018 - 4:02:57 PM

File

LAGOS-king-code (1).pdf
Files produced by the author(s)

Identifiers

Citation

Rennan Dantas, Rudini Sampaio, Frédéric Havet. Minimum density of identifying codes of king grids. Electronic Notes in Discrete Mathematics, Elsevier, 2017, 62, pp.51 - 56. ⟨10.1016/j.endm.2017.10.010⟩. ⟨hal-01634305⟩

Share

Metrics

Record views

503

Files downloads

74