Minimum density of identifying codes of king grids

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.