Minimum density of identifying codes of king grids

Rennan Dantas 1 Frédéric Havet 2 Rudini Sampaio 1
2 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 products of two paths. We show that for every king grid G, d * (G) ≥ 2/9 = 0.222. In addition, we show that this bound is attained only for king grids which are strong products of two infinite paths. Given a positive integer k, we denote by K k the (infinite) king strip with k rows. We prove that d * (K 3) = 1/3 = 0.333, d * (K 4) = 5/16 = 0.3125, d * (K 5) = 0.2666 and d * (K 6) = 5/18 = 0.2777. 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

https://hal.inria.fr/hal-01861913
Contributor : Frederic Havet <>
Submitted on : Friday, December 21, 2018 - 8:57:59 AM
Last modification on : Friday, December 21, 2018 - 9:54:19 AM
Long-term archiving on : Friday, March 22, 2019 - 2:53:57 PM

File

idcodes-king.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Rennan Dantas, Frédéric Havet, Rudini Sampaio. Minimum density of identifying codes of king grids. Discrete Mathematics, Elsevier, 2018, 341 (10), pp.2708 - 2719. ⟨10.1016/j.disc.2018.06.035⟩. ⟨hal-01861913⟩

Share

Metrics

Record views

223

Files downloads

90