O Número de Helly na Convexidade Geodética em Grafos

Palestrante: Prof. Moisés Teles Carvalho Junior, Instituto Benjamin Constant.

Data: 29 de junho de 2016, 13h30.

Local: Sala 407, Bloco H, 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.