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
-
.png)
21/08 a 10/11/2023
Encontros Universitários 2023
-
24/08 a 18/12/2023
Monitoria 2023.2 - Álgebra Linear
-
24/08 a 18/12/2023
Monitoria 2023.2 - Estrutura de Dados
-
24/08 a 18/12/2023
Monitoria 2023.2 - Algoritmos e Complexidade Computacional
-
24/08 a 18/12/2023
Monitoria 2023.2 - Fisica Geral I
-
24/08 a 18/12/2023
Monitoria 2023.2 - Fisíca Geral II
-
24/08 a 18/12/2023
Monitoria 2023.2 - Fundamentos de Programação
-
25/10 a 26/10/2023
5ª Semana do Livro e da Biblioteca
-
31/10 a 31/10/2023
Como se preparar para apresentações em público