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 Kk the (infinite) king strip with k rows. We prove that d∗(K3)=1∕3=0.333, d∗(K4)=5∕16=0.3125, d∗(K5)=4∕15=0.2666 and d∗(K6)=5∕18=0.2777. We also prove that 29+881k≤d∗(Kk)≤29+49k for every k≥7.