C. Since, C, then (1, 2) is satisfied by (1, 1) and (0, 3) at Rule 2a (since (0, 3) has at most four neighbors in U , none of them in U 1 ) If (0, 2) ? C, then (1, 2) is satisfied by (1, 1) and (0, 2) at Rule 2a (since C[(0, 1)] = C[(1, 1)] implies that either (?1, 1) ? C or (?1, 2) ? C and consequently (0, 2) has at most four neighbors in U , none of them in U 1 ) and (2, 3) receives charge 1/2 from (1, 3) at Rule 2c, both cases) is satisfied at Rule 2b by (1, 1) and either (0, 3) or (0, 2), and (2, 3) receives charge 1/2 from then u ?2 (v) ? 2, and v satisfies Eq

. Proof, C. Let, and U. , We want to prove by the discharging method that the density of C in V (T k ) is at least 1/4 + 1/4k Every vertex of C begins with charge 1 and every vertex of U begins with charge 0 We say that a vertex (x, y) ? V (T k ) is in the border if y ? {1, k}; otherwise it is in the center If v is in the center, exc(v) = chrg(v) ? 1/4. If v is in the border, exc(v) = chrg(v) ? 3/8. We say that a vertex v is satisfied if exc(v) ? 0. We will prove that, after the application of some discharging rules, every vertex of T k will be satisfied, and we are done, since ((k ? 2) Given a vertex v of T k , let B 1 (v) be the set of neighbors of v in the border and let B 2 (v) be the set of vertices in the border that are at distance 2 of v. When we say that v sends full-excess (resp. half-excess) to B i (v), this means that v sends exc(v)/b (resp. exc(v)/(2b)) to every unsatisfied vertex of B i (v), where b is the number of unsatisfied vertices of B i (v)

S. Haim and . Litsyn, Exact minimum density of codes identifying vertices in the square grid, SIAM J. Discrete Math, pp.69-82, 2005.

M. Bouznif, F. Havet, and M. Preissman, Minimum-Density Identifying Codes in Square Grids, Proceedings of AAIM 2016, pp.77-88, 2016.
DOI : 10.1007/978-3-319-41168-2_7

URL : https://hal.archives-ouvertes.fr/hal-01259550

G. Cohen, S. Gravier, I. Honkala, A. Lobstein, M. Mollard et al., Improved identifying codes for the grid

G. Cohen, I. Honkala, A. Lobstein, and G. Zemor, Bounds for Codes Identifying Vertices in the Hexagonal Grid, SIAM Journal on Discrete Mathematics, vol.13, issue.4, pp.492-504, 2000.
DOI : 10.1137/S0895480199360990

G. Cohen, I. Honkala, A. Lobstein, and G. Zémor, New bounds for codes identifying vertices in graphs, Electronic Journal of Combinatorics, vol.6, issue.1, p.19, 1999.

D. W. Cranston and G. Yu, A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid, Electronic Journal of Combinatorics, vol.16, 2009.

A. Cukierman and G. Yu, New bounds on the minimum density of an identifying code for the infinite hexagonal grid, Discrete Applied Mathematics, vol.161, issue.18, pp.2910-2924, 2013.
DOI : 10.1016/j.dam.2013.06.002

M. Daniel, S. Gravier, and J. Moncel, Identifying codes in some subgraphs of the square lattice, Theoretical Computer Science, vol.319, issue.1-3, pp.411-421, 2004.
DOI : 10.1016/j.tcs.2004.02.007

M. Karpovsky, K. Chakrabarty, and L. B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Transactions on Information Theory, vol.44, issue.2, pp.599-611, 1998.
DOI : 10.1109/18.661507

S. Ray, D. Starobinski, A. Trachtenberg, and R. Ungrangsi, Robust Location Detection With Sensor Networks, IEEE Journal on Selected Areas in Communications, vol.22, issue.6, pp.1016-1025, 2004.
DOI : 10.1109/JSAC.2004.830895

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=