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
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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
Complete list of metadatas

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
Long-term archiving on : Wednesday, February 14, 2018 - 4:02:57 PM

File

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

Identifiers

Collections

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

647

Files downloads

157