Título:Densidade Mínima de Códigos de Identificação em Grades

Data: 28/06/2019

Horário: 14:00h

Local: Sala de Seminários - Bloco 952

Resumo:

Um conjunto $C\subset V(G)$ é um código de identificação em um grafo $G$ se para todo $v\in V(G)$, $C[v]\ne\emptyset$ e, para todos $u,v\in V(G)$ distintos, $C[u]\ne C[v]$, onde $C[v]=N[v]\cap 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 $T_k$ 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\ge 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 $K_k$ 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(K_k) ≤ 2/9 +4/9k$ para todo $k ≥ 7$.

Banca:

• Prof. Dr. Rudini Menezes Sampaio (MDCC/UFC - Orientador)
• Prof. Dr. Sulamita Klein (UFRJ)
• Prof. Dr. Cláudia Linhares Sales (MDCC/UFC)
• Prof. Dr. Júlio César Silva Araújo (DMAT/UFC)
• Prof. Dr. Nicolas Almeida Martins (IEDS/Unilab)
• Prof. Dr. Antônio Josefran de Oliveira Bastos (UFC-Sobral)