Título: Densidade mínima de Códigos de Identificação em grades

Data: 08/03/2019

Horário: 14:00h

Local: Sala de Seminários - Bloco 952

Resumo:

Um conjunto C ⊆ V (G) é um código de identificação em um grafo G se para todo v ∈ V (G), C[v] é diferente de vazio e, para todos u, v ∈ V (G) distintos, C[u] é diferente C[v], onde C[v] = N [v]∩C e N [v] denota a vizinhança fechada de v em G. A densidade mínima de um código de identificação em G é denotada por d*(G). Dado um inteiro positivo k, seja Tk a grade triangular infinita com k linhas. Neste trabalho, provamos que d*(T1) = d*(T2) = 1/2, d*(T3) =d*(T4) = 1/3, d*(T5) = 3/10, d*(T6) = 1/3 e d*(Tk) = 1/4 + 1/(4k) para todo k ≥ 7 ímpar. Além disso, provamos que 1/4 + 1/(4k) ≤ d*(Tk) ≤ 1/4 + 1/(2k) para todo k ≥ 8 par. Conjecturamos que d*(Tk) = 1/4 + 1/(2k) para todo k ≥ 8 par. Neste trabalho, estudamos também a densidade de grades king. Nós mostramos que para toda grade king G, d*(G) ≥ 2/9. Além disso, mostramos que esse limite é alcançado somente para grades king que são produtos forte de dois caminhos infinitos. Dado um inteiro positivo k, denotamos por Kk a grade king com k linhas. Nós provamos que d*(K3) = 1/3, d*(K4) = 5/16, d*(K5) = 4/15 e d*(K6) = 5/18. Nós também provamos que 2/9 + 8/(81k) ≤ d*(Kk) ≤ 2/9 + 4/(9k) para todo k ≥ 7.

Banca:

• Prof. Dr. Rudini Menezes Sampaio (MDCC/UFC - Orientador)
• Prof.ª Dr.ª Cláudia Linhares Sales (MDCC/UFC)
• Prof. Dr. Júlio César Silva Araújo (UFC)