### Minimum density of identifying codes in grids

###### Apresentação

Resumo: 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). Given a positive integer k, let Tk be the triangular grid with k rows. In this work, we prove that d*(T1) = d*(T2) = 1/2, d*(T3) = d*(T4) = 1/3, d*(T5) = 3/10, d*(T6) = 1/3 and d*(Tk) = 1/4 + 1/(4k) for every k ≥ 7 odd. Moreover, we prove that 1/4 + 1/(4k) ≤ d*(Tk) ≤ 1/4 + 1/(2k) for every k ≥ 8 even. We conjecture that d*(Tk) = 1/4 + 1/(2k) for every k ≥ 8 even. We also 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, d*(T6)=1/3 and d*(Tk)=1/4 + 1/(4k) for every k ≥ 7 odd. Moreover, we prove that 1/4 + 1/(4k) ≤ d*(Tk) ≤ 1/4 + 1/(2k) for every k ≥ 8 even. We conjecture that d*(Tk) = 1/4 + 1/(2k) for every k ≥ 8 even.

###### Programação

Apresentação: "Minimum density of identifying codes in grids"

• Rennan Ferreira Dantas
• Sala 04
• 02 horas