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

Um subconjunto de vértices S de um grafo G e 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 e 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 arvores, ciclos, grafos k-partidos completos, grades completas de dimensão de grafos prisma. Mostramos também uma caracterização para grafos completos Kn, um limitante inferior e superior para o parâmetro e também que decidir se um grafo e p-Helly e co-NP-completo para p variável. 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 especificas. 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.