Estudio de la constante de hiperbolicidad en grafos

Abstract

Esta tesis se dedica al estudio de los grafos hiperbólicos y está dividida en cuatro capítulos. El primer capítulo es una intoducción a la teoría de grafos y a los espacios hiperbólicos en sentido de Gromov. En los demás capítulos se incluyen los resultados de investigación que hemos conseguido. Aunque se dispone de ejemplos interesantes de espacios hiperbólicos, no existen criterios generales que permitan determinar la hiperbolicidad de un espacio. Por tanto, uno de los problemas más importantes en el estudio de los grafos hiperbólicos es obtener criterios que garanticen si un determinado grafo es hiperbólico o no. Por otra parte, existen numerosos parámetros en teoría de grafos que tienen gran importancia, tales como: el número de vértices, el núumero de aristas, el grado máximo, el grado mínimo, el diámetro, el cuello,... Por tanto, otro problema tan natural como importante es encontrar desigualdades que relacionen alguno de estos parámetros (o varios de ellos simultáneamente) con la constante de hiperbolicidad del grafo, encontrando y clasificando (como es importante en teoría de grafos) aquellos grafos para los que se tenga la igualdad. En esta tesis se demuestra que el estudio de la hiperbolicidad de los grafos se puede reducir al estudio de la hiperbolicidad de grafos más sencillos. En particular, hemos demostrado que el estudio de la hiperbolicidad de un grafo G con lazos y aristas múltiples se puede reducir al estudio de la hiperbolicidad del grafo obtenido al eliminar de G sus lazos y aristas múltiples; también se demuestra que el estudio de la hiperbolicidad de un grafo arbitrario es equivalente al estudio de la hiperbolicidad de un grafo 3-regular obtenido añadiendo algunas aristas y vértices. En resumen, probamos que el estudio de la hiperbolicidad para grafos generales (posiblemente con lazos y aristas múltiples) se reduce al estudio de la hiperbolicidad de grafos cúbicos sin lazos ni aristas múltiples. Adicionalmente, se estudia cómo la constante de hiperbolicidad de un grafo puede cambiar añadiendo o eliminando una cantidad finita o infinita de aristas.