Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8902848 | Discrete Mathematics | 2018 | 12 Pages |
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 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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Rennan Dantas, Frédéric Havet, Rudini M. Sampaio,