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 ,
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) ,
Exact minimum density of codes identifying vertices in the square grid, SIAM J. Discrete Math, pp.69-82, 2005. ,
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
Improved identifying codes for the grid ,
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
New bounds for codes identifying vertices in graphs, Electronic Journal of Combinatorics, vol.6, issue.1, p.19, 1999. ,
A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid, Electronic Journal of Combinatorics, vol.16, 2009. ,
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
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
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
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=10.1.1.4.6722