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 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 81 k ≤ d ⁎ ( K k ) ≤ 2 9 + 4 9 k for every k ≥ 7 .