Skip to Main content Skip to Navigation
Journal articles

Minimum density of identifying codes of king grids

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.
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 : Friday, March 27, 2020 - 4:02:11 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

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

751

Files downloads

322