Identifying codes of Archimedean grids

Overview & Synopsis

An identifying code of a graph is a dominating set $C$ such that the sets $N[v]\cap C$ are pairwise distinct. The minimum density of an identifying code has been studied extensively for several infinite grids. It is known to be $1/4$ for the triangular grid and $7/20$ for the square grid, whereas for the hexagonal grid the problem is still open, between $5/12$ and $53/126$. These three grids are the regular members of the family of the eleven Archimedean grids. In this paper, we start a systematic study of identifying codes in this family. We determine the minimum density for five of the nine Archimedean grids for which it was not known: it is $2/3$ for the truncated hexagonal grid 3.12.12, $3/7$ for the truncated square grid 4.8.8, and $1/3$ for the trihexagonal (kagome) grid 3.6.3.6, the elongated triangular grid $3^3.4^2$ and the snub hexagonal grid $3^4.6$. All lower bounds are proved by the discharging method. For the three remaining non-regular Archimedean grids, we also obtain some bounds: the minimum density lies between $3/7$ and $13/30$ for the truncated trihexagonal grid 4.6.12, between $1/3$ and $11/30$ for the rhombitrihexagonal grid 3.4.6.4, and between $2/7$ and $9/28$ for the snub square grid $3^2.4.3.4$.