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.
Document type :
Journal articles
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01634305
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Monday, November 13, 2017 - 10:41:00 PM
Last modification on : Tuesday, October 19, 2021 - 11:15:48 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

970

Files downloads

872