voltarData: 29/06/2016
Titulo: O Número de Helly na Convexidade Geodética em Grafos
Palestrante: Prof. D.Sc. Moisés Teles Carvalho Junior, Instituto Benjamin Constant
Data: 29 de junho de 2016, 13h30
Local: Campus Gragoatá, IME, UFF
Resumo: Um subconjunto de vértices S de um grafo G é geodeticamente convexo se todos os vértices de qualquer caminho mínimo entre dois vértices de S pertencem a S. O parâmetro conhecido como número de Helly de um grafo G na convexidade geodética é o menor inteiro k para o qual toda família C de conjuntos geodeticamente convexos k-intersectantes de G, possui um vértice comum a todos os conjuntos de C. Neste trabalho determinamos o número de Helly de algumas classes de grafos, como as árvores, ciclos, grafos k-partidos completos, grades completas de dimensão d, e grafos prisma. Mostramos também uma caracterização para grafos completos Kn e um limitante inferior para o parâmetro. Além disso, apresentamos também alguns teoremas cuja aplicação possibilita a eliminação de subgrafos que facilitem o cálculo para grafos com características específicas. Finalmente, são apresentados teoremas que permitem a decomposição do grafo onde ao menos uma das componentes conexas herda o número de Helly geodético do grafo original.
Confira aqui a apresentação